[Solution] Minimum Coloring solution codechef

Minimum Coloring solution codechef – There is a matrix of size N×MN×M. Two distinct cells of the matrix (x1,y1)(x1,y1) and (x2,y2)(x2,y2) are painted with colors 11 and 22 respectively.

You have to paint the remaining cells of the matrix such that:

  • No two adjacent cells are painted in same color.
  • Each color is an integer from 11 to 109109 (both inclusive).
  • The number of distinct colors used is minimum (including 11 and 22).

Minimum Coloring solution codechef

  1. You cannot repaint the cells (x1,y1)(x1,y1) and (x2,y2)(x2,y2).
  2. Two cells are adjacent if they share a common edge. Thus, for a cell (x,y)(x,y) there are 44 adjacent cells. The adjacent cells are (x,y+1),(x,y1),(x+1,y),(x,y+1),(x,y−1),(x+1,y), and (x1,y)(x−1,y).

Input Format

  • First line will contain TT, number of test cases. Then the test cases follow. Each test case consists of 33 lines.
  • The first line contains two space seperated integers NN and MM denoting the dimensions of the matrix.
  • The second line contains two integers x1x1 and y1y1, denoting the coordinates of cell which is painted 11.
  • The third line contains two integers x2x2 and y2y2, denoting the coordinates of cell which is painted 22.

Output Format

For each test case, output NN lines, each consisting of MM space separated integers where jthjth integer in ithith line denotes the color of cell in ithith row and jthjth column of the matrix and must be in [1,109][1,109] inclusive.

In case of multiple possible answers, output any.

Minimum Coloring solution codechef

  • 1T1001≤T≤100
  • 2N,M1052≤N,M≤105
  • 1x1,x2N1≤x1,x2≤N
  • 1y1,y2M1≤y1,y2≤M
  • (x1,y1)(x2,y2)(x1,y1)≠(x2,y2)
  • Sum of NMN⋅M over all test cases does not exceed 105105.

Sample Input 1 

2
2 2
1 1
2 2
2 3
1 1
1 2

Minimum Coloring solution codechef

 

1 4
4 2
1 2 1
2 1 2

Minimum Coloring Explanation

Test Case 11:
Minimum Coloring solution codechef
The initially painted cells are (1,1)(1,1) and (2,2)(2,2). One possible way is to paint the remaining cells with color 44. This way, no two adjacent cells have the same color.
Note that, instead of color 44, we can use any other color in the range [1,109][1,109] except colors 11 and 22.
The number of distinct colors used in this case is 33. It can be shown that the minimum number of distinct colors cannot be less than 33.

Test Case 22:

The initially painted cells are (1,1)(1,1) and (1,2)(1,2). One possible way is to paint the remaining cells as shown in the figure. This way, no two adjacent cells have the same color.
The number of distinct colors used in this case is 22. It can be shown that the minimum number of distinct colors cannot be less than 22.

Leave a Comment