50032. N-pieces (special judge)

I'm a slow walker, but I never walk backwards.

Problem Description

Given a chessboard of $n$ by $n$, is it possible to place m pieces in it so that no more than $k$ pieces appear in each row, each column, and each 45 degree line? Note that there are two 45 degree lines for a cell $(x, y)$ not in the corners. That is, the first one goes through … $(x-1, y + 1)$, $(x, y)$, $(x + 1, y -1)$, … and the second one goes through $(x + 1, y + 1)$, $(x, y)$, $(x - 1, y - 1)$, …

p10074-boardp10074-board

p10074-limitp10074-limit

Subtasks

  • 5pt. $n = 3$, $m = 4$, and $k = 2$.
  • 5pt. $n = 3$, $m = 3$, and $k = 1$.
  • 15pt. $n = 6$, $m = 6$, and $k = 1$.
  • 20pt. $n$ is no more than 8, $m$ is no more than 16, and $k$ is no more than 1.
  • 50pt. $n$ is no more than 12, $m$ is no more than 30, and $k$ is no more than 10.
  • 5pt. $n$ is no more than 15, $m$ is no more than 100, and $k$ is no more than 100.

Hints

  • You simply try to place the pieces into each cell in a row by row manner. Each time you place a piece, you need to check if your placement is valid.
  • There are various optimizations you can use. For example, if you have placed m pieces in the same row then you should go on to the next row.
  • To get the last 5 points you need a very careful implementation that tracks the number of pieces that are already placed in each row, column a 45 degree line.

Input Format

n1 m1 k1
n2 m2 k2
...(until EOF)

For each line, you have to find out whether it is possible or not to place m pieces in a chessboard of $n$ by $n$ so that no more than $k$ pieces appear in each row, each column, and each 45 degree line.

Output Format

If it is possible to place $m$ pieces in the chessboard, print one possible solution.

If it is not possible to place m pieces in the chessboard, print N.

Sample Input

3 6 2
2 3 1
8 8 1

Sample Output

oo.
o.o
.oo
N
o.......
....o...
.......o
.....o..
..o.....
......o.
.o......
...o....

Discussion