Mine Sweeper
TimeLimit:1000MS MemoryLimit:262144KB
64-bit integer IO format:%I64d
未提交 | 登录后收藏
Problem Description
A mine-sweeper map can be expressed as an $r\times c$ grid, and each cell of the grid is either mine cell or non-mine cell. A mine cell has no number on it, while a non-mine cell has a number, the number of mine cells that share at least one common point with the cell, on it. Following is a $16\times 30$ mine-sweeper map, where flag cells denotes mine cells while blank cells denotes non-mine cells with number 0 on them.
Given an integer $S$, construct a mine-sweeper map of $r, c$ both not exceeding 25, whose sum of numbers on non-mine cells exactly equals $S$. If multiple solutions exist, print any one of them. If no solution, print "-1" in one line.
Given an integer $S$, construct a mine-sweeper map of $r, c$ both not exceeding 25, whose sum of numbers on non-mine cells exactly equals $S$. If multiple solutions exist, print any one of them. If no solution, print "-1" in one line.
Input
The first line contains one positive integer $T$ ($1\le T \le 1001$), denoting the number of test cases. For each test case:
Input one line containing one integer $S\,(0\le S \le 1000)$.
Input one line containing one integer $S\,(0\le S \le 1000)$.
Output
For each test case:
If no solution, print "-1" in one line.
If any solution exists, print two integers $r, c\,(1\le r,c \le 25)$ in the first line, denoting the size of the mine-sweeper map. Following $r$ lines each contains a string only containing "." or "X" of length $c$ where ".", "X" denote non-mine cells and mine cells respectively, denoting each row of the mine-sweeper map you construct.
Please notice that you needn't print the numbers on non-mine cells since these numbers can be determined by the output mine-sweeper map.
If no solution, print "-1" in one line.
If any solution exists, print two integers $r, c\,(1\le r,c \le 25)$ in the first line, denoting the size of the mine-sweeper map. Following $r$ lines each contains a string only containing "." or "X" of length $c$ where ".", "X" denote non-mine cells and mine cells respectively, denoting each row of the mine-sweeper map you construct.
Please notice that you needn't print the numbers on non-mine cells since these numbers can be determined by the output mine-sweeper map.
SampleInput
2 7 128
SampleOutput
2 4 X..X X... 5 19 .XXXX..XXXXX..XXXX. XX.......X....X..XX X........X....XXXX. XX.....X.X....X..XX .XXXX...XX....XXXX. Hint For the first test case, the map with numbers is as follows: X21X X211 The sum of these numbers equals 2+1+2+1+1=7.