P7724 远古档案馆（Ancient Archive）题解

思路

考虑分情况讨论。

我们可以枚举出有一个空格、两个空格、三个空格、全是空格的情况，再跑DFS，可以使用记忆化搜索进行优化。

实现

2.1：编写判断函数

为了判断目前的状态与我们需要的状态是否一致，可以直接写一个 \(\texttt{bool}\) 函数判断：

bool check(int x,int y,int z,int p){
	if(x!=b[1][1]){
		return false;
	}
	if(y!=b[1][2]){
		return false;
	}
	if(z!=b[2][1]){
		return false;
	}
	if(p!=b[2][2]){
		return false;
	}
	return true;
}

如果有一个格子不同我们可以直接return false，如果没有成功return false（即没有格子不同），那就可以return true。

因此我们可以在dfs函数中写出如下的代码：

if(check(x1,y1,x2,y2)){
	puts("Yes");
	exit(0);//强行结束整个程序
}

2.2 枚举只有一个格子为空的情况

我们用 \(k\) 表示空格子的数量。

if(k==1){
	if(y1==0){
		if(!c[0][x1][x2][y2]){
			c[0][x1][x2][y2]=1;
			dfs(0,x1,x2,y2);
		}
		if(!c[x1][y2][x2][0]){
			c[x1][y2][x2][0]=1;
			dfs(x1,y2,x2,0);
		}
		return;
	}
	if(x1==0){
		if(!c[y1][0][x2][y2]){
			c[y1][0][x2][y2]=1;
			dfs(y1,0,x2,y2);
		}
		if(!c[x2][y1][0][y2]){
			c[x2][y1][0][y2]=1;
			dfs(x2,y1,0,y2);
		}
		return;
	}
	if(x2==0){
		if(!c[0][y1][x1][y2]){
			c[0][y1][x1][y2]=1;
			dfs(0,y1,x1,y2);
		}
		if(!c[x1][y1][y2][0]){
			c[x1][y1][y2][0]=1;
			dfs(x1,y1,y2,0);
		}
		return;
	}
	if(y2==0){
		if(!c[x1][0][x2][y1]){
			c[x1][0][x2][y1]=1;
			dfs(x1,0,x2,y1);
		}
		if(!c[x1][y1][0][x2]){
			c[x1][y1][0][x2]=1;
			dfs(x1,y1,0,x2);
		}
		return;
	}
}

我们可以枚举出空的格子，对于每一种情况，可以证明有两种移动方式，我们只要对每种情况都枚举出来判断是否走过这个状态（记忆化搜索的精髓）。如果可以将记忆化数组修改再DFS这个新出现的状态。

同样的，我们可以写出有两个格子空、三个格子空情况。

2.3 四个格子空的情况怎么处理？

四个格子空的时候，我们可以在dfs函数的最后写上这样一段特判：

if(k==4){
	if(!c[0][0][0][0]){
		c[0][0][0][0]=1;
		dfs(0,0,0,0);
	}
	return;
}

把四个格子都空的情况标记了，如果最终数组不是四个空格（即check函数没有返回true）就会return掉，输出No。

2.4 没有格子空的情况怎么处理？

我们可以把check函数放在dfs函数的处理部分前面，如果check函数返回false，那么程序就会往下执行，但是我们并没有判断 \(k=0\) 的情况，程序就会直接return掉，输出No。

2.5 主函数

for(int i=1;i<=2;i++){
	for(int j=1;j<=2;j++){
		a[i][j]=read();
		if(a[i][j]==0){
			k++;
		}
	}
}
for(int i=1;i<=2;i++){
	for(int j=1;j<=2;j++){
		b[i][j]=read();
	}
}
dfs(a[1][1],a[1][2],a[2][1],a[2][2]);
puts("No");

读入一个二维数组 \(a\) 表示最初的状态，用二维数组 \(b\) 表示最终的状态，把初始状态放进dfs函数处理。如果没有输出Yes（即没有exit(0)）就输出No。

AC Code

各部分代码已经在文中详细阐述。

AC记录

赛时AC记录

洛谷题解

相关

标签