## Task Description

A knight in chess has up to eight possible *valid* moves, as shown in the following figure.

Assume that we have $m$ knights on an $n$ by $n$ chess board. The knights are indexed from $1$ to $m$. The knights will move one step at a time according to their increasing index order.

A knight decides its next move by the number of *valid* moves from the move he is about to take.
This is denoted as the $p$ value of this moves.
A *valid* move is defined as a move that it does *not* move the knight out of the board, and it does not move the knight into a cell that any knight is currently in, or has been to.
A knight will choose the move that has the *minimum* $p$-value.

We first write a function `validMoveNum`

to count the number of *valid* moves when we are given the row $r$ and column $c$ of the cell a knight is in, the board size $n$, and an array visited.
A cell in the visited array has a *non-zero* integer if the corresponding cell has been visited by any knight, and 0 otherwise.
For example, if `visited[2][5] = 0`

it means that the cell at row 2 and column 5 has not been visited by any knight.
If the given location ($r$, $c$) is out of the board or has been visited, the function should return -1, otherwise it returns the number of *valid* moves a knight at ($r$, $c$) can make.
The prototype of `validMoveNum`

function is as follow:

1 `int`

`validMoveNum(`

`int`

`r, `

`int`

`c, `

`int`

`n, `

`int`

`visited[100][100]);`

The following is an example of how `validMoveNum`

works.
Assume that the green cell is ($r$, $c$), and the grey cells are visited cells, `validMoveNum`

should return 2 because there are two *valid* moves starting from ($r$, $c$).
By definition the return value of `validMoveNum`

is the $p$-value of a move that moves the knight into ($r$, $c$).

You can check your function with this function `main_validMoveNum.c`

:

1234567891011121314151617181920212223242526272829303132 `#include <stdio.h>`

`#include "validMoveNum.h"`

`#define MAXN 100`

`int`

`r[MAXN*MAXN];`

`int`

`c[MAXN*MAXN];`

`int`

`visited[MAXN][MAXN]={0};`

`int`

`move[8][2] = {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};`

`void`

`print_p(`

`int`

`p[]){`

` `

`for`

`(`

`int`

`j=0; j<8; j++){`

` `

`printf`

`(`

`"%d"`

`,p[j]);`

` `

`if`

`(j==7)`

` `

`printf`

`(`

`"\n"`

`);`

` `

`else`

` `

`printf`

`(`

`" "`

`);`

` `

`}`

` `

`return`

`;`

`}`

`int`

`main(){`

` `

`int`

`n,m;`

` `

`scanf`

`(`

`"%d%d"`

`, &n, &m);`

` `

`for`

`(`

`int`

`i=0; i<m; i++){`

` `

`scanf`

`(`

`"%d%d"`

`, &r[i], &c[i]);`

` `

`visited[r[i]][c[i]] = 1;`

` `

`}`

` `

`int`

`p[8];`

` `

`for`

`(`

`int`

`i=0; i<m; i++){ `

`//each knight`

` `

`for`

`(`

`int`

`j=0; j<8; j++)`

` `

`p[j] = validMoveNum(r[i]+move[j][0], c[i]+move[j][1], n, visited); `

` `

`print_p(p); `

` `

`}`

` `

`return`

`0;`

`}`

After computing the $p$ values of all eight possible moves, a knight chooses the *valid* move with the minimum $p$-value.
We write a function `nextMove`

to do this.
This function `nextMove`

has four parameters, the knight’s row $r$, the knight’s column $c$, board size $n$, and an array visited, which is the same as in `validMoveNum`

.

It is obvious that `nextMove`

should call `validMoveNum`

to simplify its work.
`nextMove`

should return -1 if there is no valid move it can find.
Otherwise, it returns the index of the move (from 0 to 7) it should go, as shown in the first picture.

The prototype of function `nextMove`

is as below:

1 `int`

`nextMove(`

`int`

`r, `

`int`

`c, `

`int`

`n, `

`int`

`visited[100][100]);`

You can check your function with this function `main_nextMove.c`

:

1234567891011121314151617 `#include <stdio.h>`

`#include "nextMove.h"`

`#define MAXN 100`

`int`

`visited[MAXN][MAXN]={0};`

`int`

`move[8][2] = {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};`

`int`

`main(){`

` `

`int`

`n, m, r, c;`

` `

`scanf`

`(`

`"%d"`

`,&n);`

` `

`scanf`

`(`

`"%d%d"`

`,&r,&c);`

` `

`scanf`

`(`

`"%d"`

`,&m);`

` `

`for`

`(`

`int`

`i=0; i<m; i++){`

` `

`int`

`a,b;`

` `

`scanf`

`(`

`"%d%d"`

`,&a,&b);`

` `

`visited[a][b] = 1;`

` `

`}`

` `

`printf`

`(`

`"%d"`

`, nextMove(r, c, n, visited));`

`}`

Finally, we need to complete a **main** function which uses function `validMoveNum`

and `nextMove`

to simulate several knights’ movement.
First of all, the **main** function reads the board size $n$, number of knights $m$, and locations of all $m$ knights as inputs.
After that, the main function checks where each knight should go in increasing index order.
For every knight, we first call `validMoveNum`

to get the number of possible moves.
If there are no *valid* moves then this knight will not move.
If this knight has *valid* moves we then call `nextMove`

to find a move for him.
If all knights cannot move, the simulation stops.

## Compile

123 `gcc -O2 main_validMoveNum.c validMoveNum.c`

`gcc -O2 main_nextMove.c nextMove.c validMoveNum.c`

`gcc -O2 main.c validMoveNum.c nextMove.c`

## Input Format

For `main_validMoveNum.c`

and `main.c`

, the input format is the same and has only one test case. The first line is board size $n$ and number of knights $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.

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

For `main_nextMove.c`

, the input has only one test case as well.
The first line is the board size $n$.
The following line is the row and column of a single knight.
The third line is number of visited cells $m$, and the following $m$ lines are positions $r$ and $c$ of $m$ different visited cells.

- $1\leq n\leq 100$
- $0\leq m\leq n^{2}$

## Output Format

For `main_validMoveNum.c`

:
The output is $m$ lines of eight *valid* move numbers $p$, which are the returned values of function `validMoveNum`

of all $m$ knights, when assuming no knight moves in this case.
Note that value -1 is only returned when the location we are checking is out of board.

- $-1\leq p\leq 7$

For `main_nextMove.c`

:
The output is the index of direction $i$ where the only knight should go.
Note that value -1 is only returned when the knight has no *valid* move.

- $-1\leq i\leq 7$

For `main.c`

:
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 \textit{index} + \textit{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.

## Subtasks

- 20 points: Only the correctness of
`validMoveNum`

will be considered in these subtasks. - 30 points: Both the correctness of
`nextMove`

and`validMoveNum`

will be considered in these subtasks. - 50 points:
**main**will be checked, which means all three functions`validMoveNum`

,`nextMove`

, and`main`

should be correct in order to get all the points.

Note that if you only complete a single function, for example `validMoveNum`

, and want to submit if for a partial credits, your `main.c`

and `nextMove.c`` should be empty function so they will compile, as shown below:

1 `int`

`main(){}`

1 `int`

`nextMove(){}`

## Sample Input 1 (for validMoveNum)

`3 2`

`0 0`

`2 2`

## Sample Output 1

`-1 -1 1 1 -1 -1 -1 -1`

`-1 -1 -1 -1 -1 -1 1 1`

## Sample Input 2 (for nextMove)

`3`

`2 2`

`3`

`0 1`

`0 2`

`2 0`

## Sample Output 2

`6`

## Sample Input 3 (for main)

`3 2`

`0 0`

`2 2`

## Sample Output 3

`10000 10003 20002`

`20001 0 10001`

`10002 20003 20000`