题目还算中规中矩,就是剪枝比较麻烦。
解题思路: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;
}