首页 > 代码库 > Codevs 1004 四子连棋
Codevs 1004 四子连棋
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
数据范围及提示 Data Size & Hint
hi
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 #define Mod 9875321 7 #define maxn 1000005 8 long long read(){ 9 long long x=0,f=1;char ch=getchar();10 while(ch<‘0‘||ch>‘9‘){11 if(ch==‘-‘)f=-1;ch=getchar();12 }13 while(ch>=‘0‘&&ch<=‘9‘){14 x=x*10+ch-‘0‘;ch=getchar();15 }16 return x*f;17 }18 int head=0,tail=2,ans=-1;19 int step[maxn],xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};20 char q[maxn][5][5],a[5][5];21 bool last[maxn],mp[maxn*10];22 bool Valid(int x,int y,int t){23 //该函数用于判断与空白格子交换的合法性24 if(x>4||y>4||x<1||y<1||a[x][y]==‘O‘)return 0;25 if(a[x][y]==‘B‘&&t==0)return 0;26 if(a[x][y]==‘W‘&&t==1)return 0;27 return 1;28 }29 bool equal(char a,char b,char c,char d){30 if(a!=b || b!=c || c!=d)return 0;31 return 1;32 }33 int gethash(char a[5][5]){34 int t=0,key=0;35 for(int i=1;i<=4;i++)36 for(int j=1;j<=4;j++){37 if(a[i][j]==‘O‘)t=0;38 if(a[i][j]==‘W‘)t=1;39 if(a[i][j]==‘B‘)t=2;40 key=(key*3+t) % Mod;41 }42 return key;43 }44 bool check(char a[5][5]){45 for(int i=1;i<=4;i++){46 if(equal(a[i][1],a[i][2],a[i][3],a[i][4]))return 1;47 if(equal(a[1][i],a[2][i],a[3][i],a[4][i]))return 1;48 }49 if(equal(a[1][1],a[2][2],a[3][3],a[4][4]))return 1;50 if(equal(a[1][4],a[2][3],a[3][2],a[4][1]))return 1;51 return 0;52 }53 void Move(int x,int y){54 for(int k=0;k<4;k++){55 int tx=x+xx[k],ty=y+yy[k];56 if(!Valid(tx,ty,last[head]))continue;57 58 for(int i=1;i<=4;i++)59 for(int j=1;j<=4;j++)60 a[i][j]=q[head][i][j];61 62 swap(a[x][y],a[tx][ty]);63 if(mp[gethash(a)])continue;64 mp[gethash(a)]=1;65 tail++;66 for(int i=1;i<=4;i++)67 for(int j=1;j<=4;j++)68 q[tail][i][j]=a[i][j];69 70 step[tail]=step[head]+1;71 last[tail]=last[head]^1;72 if(check(a))ans=step[tail];73 }74 }75 void BFS(){76 while(head != tail){77 for(int i=1;i<=4;i++)78 for(int j=1;j<=4;j++)79 if(q[head][i][j]==‘O‘)80 Move(i,j);81 if(ans != -1) return;82 head++;83 }84 }85 int main()86 {87 for(int i=1;i<=4;i++)88 scanf("%s",a[i]+1);89 for(int i=1;i<=4;i++)90 for(int j=1;j<=4;j++)91 q[0][i][j]=q[1][i][j]=a[i][j];92 93 last[0]=0;last[1]=1;94 BFS();95 printf("%d\n",ans);96 return 0;97 }
Codevs 1004 四子连棋
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。