50122. Knights' Tour

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

Task Description

There are $m$ knights on an $n$ by $n$ chess board. The knights are indexed from $1$ to $m$. The knights will move one at a time according to their index order. Each time a knight will move one step, and he has up to eight possible next positions, as shown in the following figure.

Step

A knight may have multiple possible moves, and he will pick his next move as follows. He will calculate the number of possible next moves from the move he is considering. Let us call this number of moves $p$ of the next move, and a knight will choose the next move with the smallest $p$. If there are more than one move having the same minimum $p$, he will choose the one with the minimum index in the figure above. In addition, a knight cannot move into a cell other knights or himself has visited, and he cannot move out of the board. If a knight cannot find a move, he stops. The process stops when all knights stop.

The following is an example of three knights on a four by four board. The first knight moves first. Since his both next move has $p = 3$, he chooses the one with smaller move index. The second knight has three moves, but only one has $p = 1$, which is the one he will choose. The third knight has two moves, and he choose the one that has smaller $p = 2$. After the third knight moves, the first knight then moves his second step. He has two moves with the same $p = 1$, so he chooses the one with smaller move index. Following the rule, each of them will stop when he cannot find a move. Also note that the second knight stops before the first and the third knight do.

exampleexample

Input Format

The input has only one test case. The first line is $n$ and $m$. The following $m$ lines are the positions of the $m$ knights in the index order from $1$ to $m$. The format of the position is $r$ and $c$, where $r$ is the row index and $c$ is the column index.

  • $4\leq n\leq 100$
  • $1\leq m\leq n^{2}$
  • $0\leq r, c\leq n-1$

Output Format

The output is the final state of the $n$ by $n$ board. The value of each cell records the index of the knight that visited it and the step count, in the format of $\left( 10000\times index + stepCount\right) $. Note that the step count of the initial state is zero. If there are cells never visited their values should be zero. Note that there is no space at the end of each line.

Subtask

  • 10 points: There is only one knight.
  • 90 points: There are multiple knights.

Sample Input 1

4 3
3 0
0 2
0 0

Sample Output 1

30000 10004 20000 10002
20003 10001 30003 10005
30004 30001 10003 20001
10000 20002 30005 30002

Sample Input 2

5 1
2 2

Sample Output 2

10020 10011 10006 10001 10018
10005 10016 10019 10012 10007
10010 10021 10000 10017 10002
10015 10004 10023 10008 10013
10022 10009 10014 10003 10024

Discussion