题目描述
在一个4*4的棋盘上有8个黑棋和8个白棋，当且仅当两个格子有公共边，这两个格子上的棋是相邻的。移动棋子的规则是交换相邻两个棋子。现在给出一个初始棋盘和一个最终棋盘，要求你找出一个最短的移动序列使初始棋盘变为最终棋盘。
Klux说：“这么简单的题目，我都会做！”
输入格式：
第1到4行每行四个数字（1或者0），描述了初始棋盘
接着是一个空行
第6到9行每行四个数字，描述了最终棋盘
输出格式：
输出只有一行是一个整数n，表示最少的移动步数。
输入样例#1：
1111
0000
1110
0010
1010
0101
1010
0101
输出样例#1：
4
判断一种状态到另一种状态
一种是深搜，直接将初始状态和末状态记录下来，爆搜每个点的目的地，每一次搜索的代价为，abs（横坐标差值）+abs（纵坐标差值）
广搜就是模拟每一次到达的状态，因为有216种，所以需要用2进制模拟格子的交换过程，分成分成向下和向左
#include<stdio.h>
#include<queue>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define SUM 15
#define N 4
#define Line 3;
int ans,n,st,ed;
struct node
{
int num,step;
};
int vis[100000];
queue<node>q;
void bfs()
{
node u;q.push((node){st,0});while(!q.empty()){
node u=q.front();q.pop();int tmp=u.num;if(tmp==ed){
printf("%d\n",u.step);return;}for(int i=15;i>=0;i--){
int x=(15-i)/4,y=(15-i)%4,w=1<<i;int rz=1<<(i-1),dz=1<<(i-4);if(y<3&&(tmp&w)!=(tmp&rz)){
if(!vis[tmp^w^rz]){
vis[tmp^w^rz]=1;q.push((node){tmp^w^rz,u.step+1});}}if(x<3&&(tmp&w)!=(tmp&dz)){
if(!vis[tmp^w^dz]){
vis[tmp^w^dz]=1;q.push((node){
tmp^w^dz,u.step+1});}}}}
}
int main()
{
char c;for(int i=15;i>=0;i--){
cin>>c;if(c=='1')st+=1<<i;}for(int i=15;i>=0;i--){
cin>>c;if(c=='1')ed+=1<<i;}if(st==ed) printf("0\n");else bfs();return 0;
}//#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[20][20],b[50];
int sx[10],sy[10],ex[10],ey[10];
int m,n,ans=0x3f3f3f,vis[10];
void dfs(int k,int sum)
{
if(sum>ans)return;if(k>m){
ans=sum;return;}for(int i=1;i<=n;i++){
if(!vis[i]){
vis[i]=1;dfs(k+1,sum+abs(sx[k]-ex[i])+abs(sy[k]-ey[i]));vis[i]=0;}}
}
int main()
{
int i,j;for(i=0;i<4;i++)scanf("%s",a[i]);getchar();for(i=0;i<4;i++){
scanf("%s",b);for(j=0;j<strlen(b);j++){
if(b[j]<a[i][j]){
sx[++m]=i;sy[m]=j;}if(b[j]>a[i][j]){
ex[++n]=i;ey[n]=j;}}}dfs(1,0);printf("%d\n",ans);return 0;
}