Colored Domino Tilings and Cuts
Problem code: DOMNOCUT
All submissions for this problem are available.
Consider rectangular grid that composed of N rows and M columns. Colored domino tiling of the grid is some way to put lowercase English letter in each cell of the grid provided that each cell has exactly one neighbor with the same letter as in this cell. Two cells of the grid are neighbors if they share a common side. Each letter represents some color. Cut of colored domino tiling is vertical or horizontal line that divides the grid in two colored domino tilings. In other words this line should not pass between two adjacent cells with the same color.
For given N and M you should find the colored domino tiling that has the minimal possible number of cuts. If there are several solutions you should find among them the tiling that uses the minimal possible number of colors in it. If your tiling requires K colors then use first K lowercase letters of English alphabet as colors. If there are still several solutions then find any such tiling.
The first line contains a positive integer T, the number of test cases. In the following lines, T test cases follow. Every test case is a single line that contains two space separated positive integers, N and M, the sizes of the grid.
For each test case output in the first line the word "IMPOSSIBLE" without quotes if there are no tilings of the grid with N rows and M columns. Otherwise output in the first line two space separated integers, the minimal number of cuts and minimal number of colors in required tiling and then in the next N lines output the tiling itself. Each of these N lines must be composed of exactly M lowercase English letters.
1 <= T <= 3000
1 <= N, M <= 500
sum of N*M in the file <= 2,000,000
5 1 1 2 2 2 3 4 3 5 5
IMPOSSIBLE 1 2 ab ab 1 3 aab ccb 1 3 aab ccb baa bcc IMPOSSIBLE
|Time Limit:||4 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions