← 返回题目列表

AtCoder · past202203_f

F. 着色图

中文机器翻译题面 查看原题

分数: 7 点

问题陈述

高桥王国由 N 状态编号 1 to 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),至少有一对 (i,j) 这样 A_{i,j}=k.
  • 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 不垂直或水平相邻,将它们涂成相同的颜色并不违反条件。