Book of programming problems

Complexity (1-100): 25

Three squares on a board M×N are marked. Cut the board in three regions of the same area, each containing a marked square and traversable by a rook (i.e. all squares in a reagion share a side with at least one another).

Example:

aaaabc abbbbc ABCccc

A,B,C - marked squares, a,b,c - the other squares of the three regions

The input data are given in a file of the following format:

M	N
x1	y1
x2	y2
x3	y3

where M and N are the width and height of the matrix, (x_i,y_i) are the column and row numbers of marks, 1≤ i≤3.

Tests

1. Input data:
9 9
4 4
4 5
4 6

A solution (may be more solutions):
2 2 2 1 1 1 1 1 1
2 2 2 1 1 1 1 1 1
2 2 2 1 1 3 3 3 1
2 2 2 1 1 3 3 3 1
2 2 2 2 2 3 3 3 1
2 2 2 3 3 3 3 3 1
2 2 3 3 3 3 3 3 1
2 2 3 3 3 3 3 1 1
2 2 2 3 3 1 1 1 1

2. Input data:
4 6
1 2
2 1
1 1

No solution

3. Input data:
4 4
1 1
2 2
3 3

No solution