[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

分析 Analysis

搜索經典題

這道題只是看上去很難= =

首先我們要明確我們要做的事情：

輸入判斷勝局行棋狀態儲存狀態判重?

其中行棋我們有：尋找行棋位判斷是否行棋行棋

對于狀態，我們有：棋盤序列碼（Hash碼）步數行棋方

然后打一遍就過了= =

代碼 Code

  1 #include<cstdio>
  2 #include<queue>
  3 #include<iostream>
  4 #include<cstring>
  5 #define LL long long
  6 using namespace std;
  7 
  8 const int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};
  9 int HASH[100000000];
 10 // State: Map Step Last HashCode?
 11 // Input:
 12 // Play: 
 13 //        FindSpace -> Move -> Hash? -> Check? -> Push
 14 //                                             -> Print
 15 // Check:
 16 //        X? -> Y? -> LU/RU?
 17 
 18 struct MAP{
 19     LL hashcode;
 20     int map[6][6],last,step;
 21     
 22     MAP(){
 23         memset(map,0,sizeof(map));
 24         last = step = hashcode = 0;
 25     }
 26 };
 27 
 28 queue<MAP> q;
 29 
 30 bool check(MAP now){
 31     for(int i = 1;i <= 4;i++)
 32     if(now.map[i][1] == now.map[i][2] && now.map[i][2] == now.map[i][3] && now.map[i][3] == now.map[i][4] ||
 33        now.map[1][i] == now.map[2][i] && now.map[2][i] == now.map[3][i] && now.map[3][i] == now.map[4][i]){
 34         return true;
 35     }
 36     
 37     if(now.map[1][1] == now.map[2][2] && now.map[2][2] == now.map[3][3] && now.map[3][3] == now.map[4][4] ||
 38        now.map[1][4] == now.map[2][3] && now.map[2][3] == now.map[3][2] && now.map[3][2] == now.map[4][1]){
 39         return true;       
 40     }
 41     
 42     return false;
 43 }
 44 
 45 bool GETCODE(MAP now){
 46     LL &code = now.hashcode;
 47     LL cnt = 1;
 48     for(int i = 1;i <= 4;i++){
 49         for(int j = 1;j <= 4;j++){
 50             code += now.map[i][j]*cnt;
 51             cnt *= 4;
 52         }
 53     }
 54     code += now.last*cnt;
 55     code %= 42137897;
 56     
 57     if(HASH[code]) return false;
 58     else{
 59         HASH[code] = 1;
 60         return true;
 61     }
 62 }
 63 
 64 void Input(){
 65     char ctmp;
 66     MAP sta;
 67     for(int i = 1;i <= 4;i++){
 68         for(int j = 1;j <= 4;j++){
 69             cin >> ctmp;
 70             switch(ctmp){
 71                 case 'B': sta.map[i][j] = 1; break;
 72                 case 'W': sta.map[i][j] = 2; break;
 73             }
 74         }
 75     }
 76     
 77     sta.step = 0;
 78     
 79     sta.last = 1;
 80     if(GETCODE(sta)) q.push(sta);
 81     sta.last = 2;
 82     if(GETCODE(sta)) q.push(sta);
 83 }
 84 
 85 void Move(MAP now,int x,int y){
 86     for(int i = 0;i < 4;i++){
 87         int nowx = x+dir[i][0];
 88         int nowy = y+dir[i][1];
 89         
 90         if(now.map[nowx][nowy] == now.last || !now.map[nowx][nowy]) continue;
 91         
 92         MAP cnt = now;
 93         
 94         cnt.map[x][y] = cnt.map[nowx][nowy];
 95         cnt.map[nowx][nowy] = 0;
 96         cnt.last = 3-now.last;
 97         cnt.step = now.step+1;
 98         
 99         if(GETCODE(cnt)) q.push(cnt);
100     }
101 }
102 
103 void Findspace(MAP now,int &x1,int &y1,int &x2,int &y2){
104     for(int i = 1;i <= 4;i++){
105         for(int j = 1;j <= 4;j++){
106             if(!now.map[i][j]){
107                 if(x1 == -1){
108                     x1 = i,y1 = j;
109                 }else{
110                     x2 = i,y2 = j;
111                 }
112             }
113         }
114     }
115 }
116 
117 void bfs(){
118     while(!q.empty()){
119         MAP tmp = q.front();
120         q.pop();
121         
122         if(check(tmp)){
123             if(!tmp.step) printf("1");
124             else printf("%d",tmp.step);
125             return;
126         }
127         
128         int x1 = -1,x2 = -1,y1 = -1,y2 = -1;
129         
130         Findspace(tmp,x1,y1,x2,y2);
131         
132         Move(tmp,x1,y1);
133         
134         Move(tmp,x2,y2);
135     }
136 }
137 
138 int main(){
139     
140     Input();
141     bfs();
142     
143     return 0;
144 }

= =心情很差

轉載于:https://www.cnblogs.com/Chorolop/p/7325048.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/253801.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/253801.shtml
英文地址，請注明出處：http://en.pswp.cn/news/253801.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！