NC213220. 德邦国王
描述
输入描述
N K M分别表示矩阵的大小、国王的瞬移方法数量和国王的瞬间移动限定次数
接下来 K 行 Xi Yi 表示国王可以让自己和 （X + Xi， Y + Yi）上的子民位置互换
其中 X Y 表示国王当前的位置
接下来 N 行为一个矩阵，表示当前的矩阵排列
接下来 N 行为一个矩阵，表示能让国王满意的矩阵排列
矩阵仅由（0， 1， 2）组成，其中 0 表示女性子民，1 表示男性子民， 2 表示国王
1 <= N <= 51 <= K <= 81 <= M <= 15
输出描述
如果国王可以在限定次数内将矩阵变成他喜欢的样子，请你输出最小次数
反之，请你输出 -1
示例1
输入:
3 2 1 1 -1 1 1 1 0 0 0 1 2 0 1 1 1 0 0 0 1 1 0 2 1
输出:
1
说明:
示例2
输入:
3 1 1 -1 0 1 0 0 0 1 2 0 1 1 1 0 0 0 1 1 0 2 1
输出:
-1
说明:
此时国王只能往上移动，所以无法将方阵变成他喜欢的样子C++(clang++11) 解法, 执行用时: 12ms, 内存消耗: 388K, 提交时间: 2020-10-24 15:54:44
#include <bits/stdc++.h>
using namespace std;
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for (int i=t;i>=h;i--)
const int N2=50;
int a[N2],b[N2];
const int N=6;
int f[N][N],g[N][N];
int n,m,k,ans;
bool check(int x)
{
if (x>=1&&x<=n) return 1; else return 0;
}
void dfs(int x,int y,int kk)
{
int cnt=0;
rep(i,1,n)
rep(j,1,n)
{
if (f[i][j]!=g[i][j]) cnt++;
}
if (cnt-1>k-kk) return;
if (kk>=ans) return;
if (cnt==0)
{
ans=min(ans,kk);
return ;
}
rep(i,1,m)
{
if (check(x+a[i])&&check(y+b[i]))
{
swap(f[x+a[i]][y+b[i]],f[x][y]);
dfs(x+a[i],y+b[i],kk+1);
swap(f[x+a[i]][y+b[i]],f[x][y]);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>k;
rep(i,1,m)
{
cin>>a[i]>>b[i];
}
int x,y;
rep(i,1,n)
rep(j,1,n)
{
cin>>f[i][j];
if (f[i][j]==2) x=i,y=j;
}
rep(i,1,n)
rep(j,1,n) cin>>g[i][j];
ans=1e9;
dfs(x,y,0);
if (ans!=1e9) cout<<ans<<endl;
else cout<<-1<<endl;
return 0;
}