1004 四子连棋
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
在一个4*4的棋盘上摆放了14颗棋子，其中有7颗白色棋子，7颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步，黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局。
| ● | ○ | ● | |
| ○ | ● | ○ | ● |
| ● | ○ | ● | ○ |
| ○ | ● | ○ |
输入描述 Input Description
从文件中读入一个4*4的初始棋局，黑棋子用B表示，白棋子用W表示，空格地带用O表示。
输出描述 Output Description
用最少的步数移动到目标棋局的步数。
样例输入 Sample Input
BWBO
WBWB
BWBW
WBWO
样例输出 Sample Output
5
#include<iostream>
#include<cstdio>
#include<cstdio> using namespace std;
int map[][],ans,flag;
int dx[]={,-,,,},dy[]={,,,-,};
inline void dfs(int ch, int deep); inline void swap(int &a,int &b)
{
int t = a;
a = b;
b = t;
} bool check()//判断是否符合条件
{
for (int k=;k<=;k++)
{
if (map[k][]==map[k][]&&map[k][]==map[k][]&&map[k][]==map[k][])return ;
if (map[][k]==map[][k]&&map[][k]==map[][k]&&map[][k]==map[][k])return ;
}
if (map[][]==map[][]&&map[][]==map[][]&&map[][]==map[][])return ;
if (map[][]==map[][]&&map[][]==map[][]&&map[][]==map[][])return ;
return ;
} void move(int ch,int deep,int x,int y) //ch表示下一个颜色
{
for(int i=;i<=;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(map[xx][yy]==ch&&xx>&&xx<&&yy>&&yy<)
{
swap(map[x][y],map[xx][yy]);
dfs(ch,deep+);
swap(map[x][y],map[xx][yy]);
}
}
} void dfs(int ch,int deep)
{
int next=!ch;
if(flag) return;
if(ans==deep)
{
if(check()) flag=;
return;
}
for(int i=;i<=;i++)
for(int j=;j<=;j++)
if(map[i][j]==-) move(next,deep,i,j);
} int main()
{
for(int i = ; i <= ; i++)
for(int j = ; j <= ; j++)
{
char a;
cin>>a;
if(a == 'B') map[i][j] = ;
if(a == 'O') map[i][j] = -;
}
for(ans = ; flag == ; ans++)
{
dfs(, );
if(flag) break;
dfs(, );
if(flag) break;
}
printf("%d\n",ans);
}
dfs
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#define maxn 5001 using namespace std;
struct node
{
int map[][];
int f;//表示这一步走的棋子是黑还是白
};node e[];
int mm[][],tep[maxn],head=,tail=,ans=maxn,flag;
int dx[]={,,,,-};
int dy[]={,,-,,};
map<string,bool> hash; bool equ(int a1,int a2,int a3,int a4){if(a1!=a2||a2!=a3||a3!=a4||a4!=a1)return ;return ;}
bool judge(int w)
{
for(int i=;i<=;i++)
{
if(equ(e[w].map[i][],e[w].map[i][],e[w].map[i][],e[w].map[i][]))return ;
if(equ(e[w].map[][i],e[w].map[][i],e[w].map[][i],e[w].map[][i]))return ;
}
if(equ(e[w].map[][],e[w].map[][],e[w].map[][],e[w].map[][]))return ;
if(equ(e[w].map[][],e[w].map[][],e[w].map[][],e[w].map[][]))return ;
return ;
} void copy()
{
for(int k=;k<=;k++)
for(int l=;l<=;l++)
e[tail].map[k][l]=e[head].map[k][l];
} bool check(node x)//hash判重
{
string s="";
for(int i=;i<=;i++)
for(int j=;j<=;j++)
s+=x.map[i][j]+'';
if(hash[s])return true;
hash[s]=;return false;
} void Bfs()
{
while(head<tail)
{
head++;
for(int i=;i<=;i++)
for(int j=;j<=;j++)
{
if(e[head].map[i][j]==)
{
for(int cnt=;cnt<=;cnt++)
{
int x=i+dx[cnt],y=j+dy[cnt];
if(x>&&x<&&y>&&y<&&e[head].map[x][y]!=e[head].f&&e[head].map[x][y]!=)
{
++tail;
copy();
e[tail].map[x][y]=;
if(e[head].f==)
{
e[tail].f=-;
e[tail].map[i][j]=-;
}
else
{
e[tail].f=;
e[tail].map[i][j]=;
}
tep[tail]=tep[head]+;
if(judge(tail))
{
flag=;
ans=min(ans,tep[tail]);
break;//手残打成return...
}
if(check(e[tail])) tail--;
}
}
}
if(flag)break;
}
}
} int main()
{
for(int i=;i<=;i++)
for(int j=;j<=;j++)
{
char c;
cin>>c;
if(c=='W')mm[i][j]=;
else if(c=='B')mm[i][j]=-;
else mm[i][j]=;
}
for(int k=;k<maxn;k++)
for(int i=;i<=;i++)
for(int j=;j<=;j++)
{
e[].map[i][j]=mm[i][j];
e[k].f=;
tep[k]=;
}
flag=;ans=maxn;
e[].f=-;
Bfs();
hash.clear();
for(int k=;k<maxn;k++)
for(int i=;i<=;i++)
for(int j=;j<=;j++)
{
e[].map[i][j]=mm[i][j];
e[k].f=;
tep[k]=;
}
head=;tail=;flag=;
e[].f=;
Bfs();//因为一开始走黑棋白棋结果可能不一样，所以两遍
printf("%d\n",ans);
return ;
}
bfs