描述
如下图所示，在4x4的棋盘上有X和Y两种棋子各若干枚；O表示空格。
OXXY
YOOX
XOOY
XOXX
小Hi每次可以选择任意一枚棋子，将它移动到上下左右相邻的空格中。
小Hi想知道最少移动多少次可以达到胜利局面：有4个X或者4个Y连成一行、一列或者对角线(两条对角线都算胜利)。
输入
4x4的棋盘
输出
达成胜利最少需要的步数。如果小Hi无论如何也达不到胜利局面，输出-1。
样例输入
OXXY YOOX XOOY XOXX
样例输出
2
思路：
数据小，达到目标的最小步骤问题，多半是搜索。但是X,Y两个形态，那么状态压缩的话，假设0是O，1是X，2是Y，则有3^16=43046721，无法二进制处理，直接用map记录string。
数组记录关系，好简短啊。。。
#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<map> #include<queue> using namespace std; map<string,int>mp; queue<string>q; int head,tail; int a[5][5]={ {0}, {0,1,2,3}, {0,4,8,12},{0}, {3} }; int b[5][5]={ {0}, {4,8,12}, {1,2,3}, {5,10,15}, {3,6,9} }; int c[5][5]={ {0}, {3,7,11,15},{0,4,8,12},{12,13,14,15},{0,1,2,3} }; int d[5]={0,1,-1,4,-4}; using namespace std; bool check(string s) { for(int i=1;i<=2;i++)//1是列，2是行 ,a代表起始，b代表跨度。 for(int j=0;j<4;j++)//每行或者每列共4个 if(s[a[i][j]]!='O'&&s[a[i][j]]==s[a[i][j]+b[i][0]]&&s[a[i][j]]==s[a[i][j]+b[i][1]]&&s[a[i][j]]==s[a[i][j]+b[i][2]]) return true; for(int i=3;i<=4;i++)//对角线 if(s[a[i][0]]!='O'&&s[a[i][0]]==s[a[i][0]+b[i][0]]&&s[a[i][0]]==s[a[i][0]+b[i][1]]&&s[a[i][0]]==s[a[i][0]+b[i][2]]) return true; return false; } int bfs() { string s,tmp; while(!q.empty()){ s=q.front();q.pop(); if(check(s)) return mp[s]-1; for(int pos=0;pos<16;pos++) for(int j=1;j<=4;j++){ string tmp=s; if(pos==c[j][0]||pos==c[j][1]||pos==c[j][2]||pos==c[j][3]) continue; if(s[pos+d[j]]=='O'&&s[pos]!='O') { tmp=s;tmp[pos]=s[pos+d[j]];tmp[pos+d[j]]=s[pos]; if(!mp[tmp]) q.push(tmp),mp[tmp]=mp[s]+1; } } } return -1; } int main() { char c[10]; string s=""; for(int i=1;i<=4;i++){ scanf("%s",c+1); s=s+c[1]+c[2]+c[3]+c[4]; } q.push(s);mp[s]=1; printf("%d ",bfs()); return 0; }