6622 번 : Domino tiling 
 6622 번 
 6622 번 - Domino tiling 
 The aliens want to dominate the whole universe . So it comes as no surprise that their favorite game is played with domino tiles . A domino tile is a tile of size 1 × 2 with a digit 0 - 9 written on each half . Their game board is a rectangular array with a digit 0 - 9 written in each unit square . The task is to cover the whole board with the set of provided domino tiles . The tiles can be placed only if the two numbers on the tile equal the two numbers in the unit squares covered by the tile . The tiles can be placed as they are or may be rotated by 90 ◦, 180 ◦ or 270 ◦. No two tiles may overlap . You can always use only one piece of each provided tile . 
 Some tiles are already placed on the board . These must stay where they are . 
 You are to write a program that will play this game . If you do not succeed , our planet will be dominated ! 
 The input contains several descriptions of game settings . The first line of each description contains three numbers separated by one or more spaces . The first two numbers are the height M and the width N of the board . They satisfy 1 ≤ M ≤ 20 , 1 ≤ N ≤ 20 , at least one of them is even , and their product 2 ≤ M · N ≤ 110 ( guess why ) . The last number is the number of available tiles K , 1 ≤ K ≤ M · N / 2 . 
 The next line contains K pairs of space - separated integers describing the pairs of numbers on the available tiles . Each two consecutive numbers on this line are separated by at least one space . In addition , no two tiles are identical , that is , they are different ( and stay different even if one is rotated by 180 ◦). The tiles already placed on the board are not among these K tiles . 
 The following M lines contain N space - separated entries each . For every i , j , 0 ≤ i < M , 0 ≤ j < N , the jth entry in the ith row describes the place in the ith row and jth column of the gameboard . The entry is either the capital letter “ X ” if there is an already - placed tile , or a number Ai , j ( 0 ≤ Ai , j ≤ 9 ) written on the board . 
 Every description is followed by an empty line and the empty line after the last description is followed by a line containing three zeros . 
 For each game , find a way to place all tiles onto the board . If there are more solutions , output any of them . Provide the solution by a graphic representation as an M × N array with “ [ ” and “ ] ” ( square brackets ) standing for the left and right half of a horizontally placed domino , and lowercase letters “ n ” and “ u ” for the upper and lower half of a vertically placed domino . The squares covered by a tile in the input are still represented by “ X ” . After the M rows , print one line containing the number of other different solutions that exist . 
 Do not output any spaces and start a new line for each row of the gameboard . 
 If there is no solution , write a single line with the word “ impossible ” . 
 Print one empty line after the each gameboard result . 
 0 0 0 1 1 1 3 3 0 2 1 2 0 3 2 2 2 3 
 1 2 2 0 X 
 [ ] [ ] X 
 nn [ ] X 
 uu [ ] n 
 [ ] [ ] u 
 CTU Open Contest , 2011