基础算法题——德邦国王（dfs、剪枝）

德邦国王

题目还算中规中矩，就是剪枝比较麻烦。
解题思路：dfs
剪枝：
①、移动次数不超过设定值 M。
②、若有解，则后面的步骤不可大于该解的值。
③、不断查询完美矩阵与当前矩阵不同的个数 t 。
t - 1 为最快可将当前矩阵移动成完美矩阵的步数，若 t - 1 + 已经移动的步数 cnt 大于 最优解时，则该情况不必再往下移动。

AC代码

#include<bits/stdc++.h>
using namespace std;
int now[10][10], per[10][10];
int n, k, m, ans=20;
struct node{
	int dx, dy;
}p[10];

//判断 x 矩阵是否是 per 矩阵 
bool judge1(int jz[10][10], int cnt){
	int t=0;
	for(int i=1; i<=n; i++)
	for(int j=1; j<=n; j++){
		if(jz[i][j]!=per[i][j]){
			t++;
		}
	} 
	if(t>ans-cnt+1||t>m-cnt+1) return true;
	if(t==0) ans = min(cnt, ans);
	return false;
}

void dfs(int jz[10][10], int cnt, int x, int y, int z){
	if(cnt>m||cnt>=ans||judge1(jz, cnt)) 
		return;
	
	for(int i=0; i<k; i++){
		if(i==z) continue;
		int dx = p[i].dx;
		int dy = p[i].dy;
		if(x+dx<=n&&y+dy<=n&&x+dx>=1&&y+dy>=1){
			jz[x][y]=jz[x+dx][y+dy];
			jz[x+dx][y+dy]=2;
			dfs(jz, cnt+1, x+dx, y+dy, i);
			jz[x+dx][y+dy]=jz[x][y];
			jz[x][y]=2;
		}
	}
}

int main(){
	int x, y;
//	freopen("data.txt", "r", stdin);
	cin>>n>>k>>m;
	for(int i=0; i<k; i++)
		cin>>p[i].dx>>p[i].dy;
	
	for(int i=1; i<=n; i++)
	for(int j=1; j<=n; j++){
		cin>>now[i][j];
		if(now[i][j]==2) x=i,y=j;
	}
	for(int i=1; i<=n; i++)
	for(int j=1; j<=n; j++)
		cin>>per[i][j];
	
	dfs(now, 0, x, y, -1);
	if(ans!=20)
		cout<<ans<<endl;
	else
		cout<<"-1\n";
		
	return 0;
}