a290. 騎士的巡禮-2

Content

在一個 $n \times n$ 的西洋棋盤上放置 $m$ 個騎士，並依序編號為 $1 \sim m$。接下來按照編號順序依次移動騎士，在西洋棋中騎士可以移動的 8 個方向如下圖。

若每個騎士有多個方向可以移動時，他會依序下列規則挑選下一步：

從所有可能走的方向中，挑選$p$最小的一個方向移動。其中 $p$ 為選擇該方向走一步後，下一步可以選擇的方向個數。
若有多個具有最小的 $p$ 值，他會挑上圖中號碼較小的方向移動，

此外，騎士無法移動到已被踩過的位置，也不可以移動到棋盤外。若一個騎士無法找到可以移動的方向，則該騎士就會停止。當所有騎士都停止的時候程式結束，並印出棋盤的紀錄。

以下為範例一的過程記錄：

第一回合中：

$1$ 號騎士有 2 個方向可以走，兩個方向的 $p$ 值都是 $3$，因此挑選號碼比較小的方向 $1$。
$2$ 號騎士有 3 個方向可以走，其中方向 $4$ 有最小的 $p=1$。
$3$ 號騎士有 2 個方向可以走，其中方向 $4$ 有最小的 $p=2$。

所有騎士都完成第一回合後，第二回合由 $1$ 號騎士開始，依此規則走到所有騎士都無法再移動為止，途中 $2$ 號騎士停止時，下一回合 $1$ 號與 $3$ 號騎士仍繼續走。

Input

第一行輸入 $n$ 跟 $m$。

接下來 $m$ 行依序輸入騎士的起始位置 $r_i$、$c_i$。分別代表第 $i$ 個騎士的row跟coloum

$4≤n≤100$
$1≤m≤n^2$
$0≤r,c≤n−1$

Output

輸出 $N \times N$ 格棋盤最後的紀錄，每一個格子的內容為$(10000 \times 編號 + 步數)$。每個騎士初始的步數為0，未被任何騎士走訪過的格子的內容為 0。

每行數字間以空白隔開，最後不可有空白。

Sample Input #1

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

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (10%): 1.0s , <1K
公開測資點#1 (10%): 1.0s , <1K
公開測資點#2 (10%): 1.0s , <1K
公開測資點#3 (10%): 1.0s , <1K
公開測資點#4 (10%): 1.0s , <1M
公開測資點#5 (10%): 1.0s , <1M
公開測資點#6 (10%): 1.0s , <1K
公開測資點#7 (10%): 1.0s , <1K
公開測資點#8 (10%): 1.0s , <1K
公開測資點#9 (10%): 1.0s , <1M

Hint ：

Tags:

二維陣列

出處:

[管理者： zero(管理員) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」