#P7724. 远古档案馆(Ancient Archive)

远古档案馆(Ancient Archive)

题目背景

为了揭开月光能量背后的秘密,你来到了地下的远古档案馆。

远古一族的秘密与遗忘的知识悉数贮藏于这片被尘封的迷宫中,你能成功解谜,获知远古的知识吗?

题目描述

远古档案馆的中心是一个解谜:

  • 有一个 2×22\times 2 的网格,每个格子中要么有一个正整数,要么是空的;

  • 你可以进行若干次操作:每次操作中,你选择一个有正整数的格子和一个与之相邻的空格子,将正整数移到那个空格子中;

  • 给定网格的初始状态和最终状态,保证初始状态和最终状态中包含的正整数个数相同(设为 kk 个),且它们就是前 kk 个不同的正整数,问是否可以通过有限次操作从初始状态到达最终状态?

下图展示了一个包含三个正整数的网格经过两次操作的情况:

只有完成解谜,才能获得遗忘的知识,因此你希望尽快解决这个问题。

注意:网格中可能没有正整数,也可能没有空格。

输入格式

输入共包括四行,每行两个整数。

前两行描述了初始状态,后两行描述了最终状态,用 00 表示空格子。

输出格式

如果可以从初始状态到达最终状态,输出 Yes,否则输出 No

2 1
3 0
0 2
3 1

Yes

2 1
4 3
3 4
2 1

No

提示

【样例 1 解释】

如题目描述中图所示。


【样例 2 解释】

没有可移动的正整数,所以无法从初始状态到达与之不相等的最终状态。


【数据范围】

本题采用捆绑测试。

所有数据符合题目描述所述。

  • Subtask 1(40 points):不存在空格。
  • Subtask 2(60 points):无特殊限制。