題目描述

在一個4*4的棋盤上有8個黑棋和8個白棋，當且僅當兩個格子有公共邊，這兩個格子上的棋是相鄰的。移動棋子的規則是交換相鄰兩個棋子。現在給出一個初始棋盤和一個最終棋盤，要求你找出一個最短的移動序列使初始棋盤變為最終棋盤。
Klux說：“這么簡單的題目，我都會做！”

輸入

第1到4行每行四個數字（1或者0），描述了初始棋盤。
接著是一個空行。
第6到9行每行四個數字，描述了最終棋盤。

?

輸出

第一行是一個整數n，表示最少的移動步數。
接下來n行每行4個數，r1,c1,r2,c2,表示移動的兩個棋子的坐標(r1,c1),(r2,c2)（棋盤左上角的坐標為(1,1)，并且他右邊的格子為(1,2)）
如果有許多組解，你可以輸出任意一組。

?

樣例輸入

1111 0000 1110 00101010 0101 1010 0101

樣例輸出

4 1 2 2 2 1 4 2 4 3 2 4 2 4 3 4 4

---

---

【題意】

　　交換即可，但是大家要這個狀態不好標記處理，所以我們需要hash處理，這個01矩陣，不難想到我們處理成二進制來處理。

　　我們怎么處理這個題目中1,0對應的位置呢？？？我們可以用我們二維數組通用的hash方法，就是除以列寬得行號，對列寬取余得到列號的做法。

　　”交換“：如何實現？？

　　同樣地得到上下兩個坐標的位置，同時其實他們對應的二進制也是序號來記錄的，然后我們直接找到兩個位置，用異或處理就可以交換0和1的操作。

　　怎么打印這個答案呢？？

　　我認為這個題目還有一點就是記錄路徑的方法，記錄路徑是非常考驗人的，但是我們需要開一個結構體，

　　這個結構體需要記錄這次hash值對應的哪兩個坐標進行交換了，同時這個結構體能通過最終狀態的hash值回溯輸出。

【代碼】：

　　

1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = (1<<16)+10; 4 int pre[N],vis[N]; 5 typedef struct Node { 6 int x,y,px,py ; 7 int pre_Num ; 8 }Node ; 9 Node ans[N]; 10 int n,m; 11 void dfs(int No){ 12 if( ans[No].pre_Num != n ) 13 dfs(ans[No].pre_Num); 14 printf("%d %d %d %d\n",ans[No].x,ans[No].y,ans[No].px,ans[No].py); 15 } 16 void BFS(){ 17 queue < int > Q ; 18 Q.push ( n ); 19 while ( !Q.empty() ) { 20 int cur = Q.front(); 21 Q.pop(); 22 // 上下互換 23 for(int i=0;i<=11;i++){ 24 int u = ( cur & (1<<i) ) >> i ; 25 int v = ( cur & (1<<i+4) ) >> (i+4); 26 int tmp = ( 1<<(i+4) ) + (1<<i) ; 27 if ( u != v ){ 28 int next = cur ^ tmp ; 29 if( vis[next] == 0 ){ 30 ans[next].x = i / 4 + 1 ; 31 ans[next].px = ans[next].x + 1 ; 32 ans[next].y = ans[next].py = i % 4 + 1 ; 33 ans[next].pre_Num = cur ; 34 vis[next] = vis[cur] + 1 ; 35 Q.push(next); 36 if ( next == m ){ 37 printf("%d\n",vis[m]); 38 dfs(next); 39 return ; 40 } 41 } 42 } 43 } 44 // 左右互換 45 for(int i=0;i<=15;i++){ 46 if(i%4==3) continue ; 47 int u = ( cur & (1<<i) ) >> i ; 48 int v = ( cur & (1<<(i+1)) ) >> (i+1); 49 int tmp = ( 1<<(i+1) ) + (1<<i) ; 50 if ( u != v ){ 51 int next = cur ^ tmp ; 52 if( vis[next] == 0 ){ 53 ans[next].px = ans[next].x = i / 4 + 1 ; 54 ans[next].y = i % 4 + 1 ; 55 ans[next].py = i % 4 + 2 ; 56 ans[next].pre_Num = cur ; 57 vis[next] = vis[cur] + 1 ; 58 Q.push(next); 59 if ( next == m ){ 60 printf("%d\n",vis[m]); 61 dfs(next); 62 return ; 63 } 64 } 65 } 66 } 67 } 68 } 69 int main() 70 { 71 for(int i=0,x;i<16;i++){ 72 scanf("%1d",&x); 73 n += x * (1<<i); 74 } 75 for(int i=0,x;i<16;i++){ 76 scanf("%1d",&x); 77 m += x * (1<<i); 78 } 79 if ( n==m ){ 80 return 0*puts("0"); 81 }else{ 82 BFS(); 83 } 84 return 0; 85 } 86 87 /* 88 89 1111 90 0000 91 1110 92 0010 93 94 1010 95 0101 96 1010 97 0101 98 99 */ 棋盤游戲

?

轉載于:https://www.cnblogs.com/Osea/p/11215746.html

總結

以上是生活随笔為你收集整理的【广搜】棋盘游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。