luogu#P7724. 远古档案馆(Ancient Archive)
远古档案馆(Ancient Archive)
题目背景
为了揭开月光能量背后的秘密,你来到了地下的远古档案馆。
远古一族的秘密与遗忘的知识悉数贮藏于这片被尘封的迷宫中,你能成功解谜,获知远古的知识吗?
题目描述
远古档案馆的中心是一个解谜:
-
有一个 的网格,每个格子中要么有一个正整数,要么是空的;
-
你可以进行若干次操作:每次操作中,你选择一个有正整数的格子和一个与之相邻的空格子,将正整数移到那个空格子中;
-
给定网格的初始状态和最终状态,保证初始状态和最终状态中包含的正整数个数相同(设为 个),且它们就是前 个不同的正整数,问是否可以通过有限次操作从初始状态到达最终状态?
下图展示了一个包含三个正整数的网格经过两次操作的情况:
只有完成解谜,才能获得遗忘的知识,因此你希望尽快解决这个问题。
注意:网格中可能没有正整数,也可能没有空格。
输入格式
输入共包括四行,每行两个整数。
前两行描述了初始状态,后两行描述了最终状态,用 表示空格子。
输出格式
如果可以从初始状态到达最终状态,输出 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):无特殊限制。