/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 7 点
問題文
高橋王国は 1 から N までの番号がついた N 個の州からなります。
高橋王国の地図は H 行 W 列のマス目の形をしていて、上から i 行目、左から j 列目のマスは州 A_{i,j} です。
この地図の州 i を色 C_i で塗るとき、以下の条件は満たされていますか？
異なる州が上下左右に隣り合っているならば、それらの州は異なる色で塗られている
制約
- 1 \leq H \leq 200
- 1 \leq W \leq 200
- 1\leq N \leq \min(100,H\times W)
- 1\leq A_{i,j} \leq N
- 全ての k(1\leq k\leq N) について、A_{i,j}=k を満たす (i,j) が少なくとも 1 つ存在する
- 1\leq C_i \leq N
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
H W N
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}
C_1 C_2 \ldots C_N
出力
条件が満たされているならば Yes と、満たされていないならば No と出力せよ。
入力例 1
2 4 3 1 1 2 3 1 2 2 3 2 3 3
出力例 1
No
州 2 と州 3 は隣り合っていますが同じ色で塗られているので、条件を満たしません。
入力例 2
3 5 4 1 1 1 3 2 1 2 1 3 4 1 1 1 3 2 3 1 4 3
出力例 2
Yes
州 1 のように穴が空いている場合もあります。
また、州 2 のように非連結である場合もあります。
入力例 3
2 2 3 1 2 3 1 1 2 2
出力例 3
Yes
州 2 と州 3 は上下左右に隣り合っていないので、同じ色で塗られていても条件を満たします。
Score : 7 points
Problem Statement
The Kingdom of Takahashi consists of N states numbered 1 to N.
The map of the kingdom is a grid with H rows and W columns. The square at the i-th row from the top and j-th column from the left belongs to State A_{i,j}.
Is the condition below satisfied when painting State i in Color C_i in this map?
Different states that are vertically or horizontally adjacent are painted in different colors.
Constraints
- 1 \leq H \leq 200
- 1 \leq W \leq 200
- 1\leq N \leq \min(100,H\times W)
- 1\leq A_{i,j} \leq N
- For every k(1\leq k\leq N), there is at least one pair (i,j) such that A_{i,j}=k.
- 1\leq C_i \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
H W N
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}
C_1 C_2 \ldots C_N
Output
If the condition is satisfied, print Yes; otherwise, print No.
Sample Input 1
2 4 3 1 1 2 3 1 2 2 3 2 3 3
Sample Output 1
No
State 2 and State 3 are adjacent but painted in the same color, so the condition is not satisfied.
(In the figure below, "色" means color.)
Sample Input 2
3 5 4 1 1 1 3 2 1 2 1 3 4 1 1 1 3 2 3 1 4 3
Sample Output 2
Yes
Some states, such as State 1 here, may have holes. Also, some states, such as State 2 here, may be disconnected.
Sample Input 3
2 2 3 1 2 3 1 1 2 2
Sample Output 3
Yes
Since State 2 and State 3 are not vertically or horizontally adjacent, painting them in the same color does not violate the condition.