題目描述
你玩過(guò)華容道的游戲嗎？這是個(gè)類似的，但更簡(jiǎn)單的游戲。看下面 3 x 2 的格子

在其中放5張牌，其中A代表關(guān)羽，B代表張飛，* 代表士兵。還有一個(gè)格子是空著的。
你可以把一張牌移動(dòng)到相鄰的空格中去(對(duì)角不算相鄰)。
游戲的目標(biāo)是：關(guān)羽和張飛交換位置，其它的牌隨便在哪里都可以。
輸入
輸入存在多組測(cè)試數(shù)據(jù)，對(duì)于每組測(cè)試數(shù)據(jù)：
輸入兩行6個(gè)字符表示當(dāng)前的局面
輸出
對(duì)于每組測(cè)試數(shù)據(jù)輸出一個(gè)整數(shù)表示答案

解題思路：

fir//表示最開始的情況 tem//上一步的情況 now//表示現(xiàn)在的情況

為了避免避免出現(xiàn)重復(fù)的形況而無(wú)限循環(huán)無(wú)結(jié)果的情況，我們可以用一個(gè)vis數(shù)組用來(lái)標(biāo)記，只要我們標(biāo)記A,B，空格的位置標(biāo)示這個(gè)情況已經(jīng)出現(xiàn)過(guò)，以后就不會(huì)出現(xiàn)同樣的情況了。
在這里由于要讀入空格，我們用gets來(lái)讀入。
以下兩種讀入的方法遇到空格都會(huì)停下來(lái)。

char s[5][5]; scanf("%s",s[0]); cin>>s[0];

如果現(xiàn)在的情況的空格位置與上一步的A的位置相同，那么現(xiàn)在的情況的A位置應(yīng)該是上一步的空格位置，同理，如果現(xiàn)在的情況的空格位置與上一步的B的位置相同，那么現(xiàn)在的情況的B位置應(yīng)該是上一步的空格位置，代碼如下：

if (xx==tem.ax && yy==tem.ay){now.ax = tem.kx;now.ay = tem.ky;}else{now.ax = tem.ax;now.ay = tem.ay;}if (xx==tem.bx && yy==tem.by){now.bx = tem.kx;now.by = tem.ky;}else{now.bx = tem.bx;now.by = tem.by;}

終止條件便是現(xiàn)在的A的坐標(biāo)與最開始的B坐標(biāo)相同，現(xiàn)在的B坐標(biāo)與最開始的A坐標(biāo)相同

if (now.ax== fir.bx && now.ay==fir.by && now.bx==fir.ax && now.by==fir.ay)

在這道題中，之所以要到最后面才開始檢查有沒(méi)有這種情況出現(xiàn)，是因?yàn)橐哌^(guò)才能得到這種情況是什么樣子的。不然你vis[now.ax][now.ay][now.bx][now.by][now.kx][now.ky]里面的now.ax,now.ay的值怎么得到。

代碼如下：

#include <iostream> #include <cstring> #include <queue> using namespace std; const int N = 8; char s[N][N]; bool vis[N][N][N][N][N][N]; int dx[] = {0,0,1,-1},dy[] = {1,-1,0,0}; struct node {int ax,ay,bx,by,kx,ky,step; };int bfs(node fir) {memset(vis,0,sizeof(vis));queue<node>q;fir.step = 0;vis[fir.ax][fir.ay][fir.bx][fir.by][fir.kx][fir.ky] = true;q.push(fir);while(q.size()){node tem = q.front();q.pop();for (int i = 0;i<4;i++){int xx = tem.kx+dx[i],yy = tem.ky+dy[i];if (xx >= 0 && xx <2 && yy >= 0 && yy <3){node now;now.kx = xx;now.ky = yy;now.step = tem.step+1;if (xx==tem.ax && yy==tem.ay){now.ax = tem.kx;now.ay = tem.ky;}else{now.ax = tem.ax;now.ay = tem.ay;}if (xx==tem.bx && yy==tem.by){now.bx = tem.kx;now.by = tem.ky;}else{now.bx = tem.bx;now.by = tem.by;}if (now.ax== fir.bx && now.ay==fir.by && now.bx==fir.ax && now.by==fir.ay){return now.step;}if (vis[now.ax][now.ay][now.bx][now.by][now.kx][now.ky]==0){vis[now.ax][now.ay][now.bx][now.by][now.kx][now.ky] = true;q.push(now);}}}}return -1; }int main() {while(gets(s[0])!=NULL){gets(s[1]);node fir;for (int i = 0;i<2;i++)for (int j = 0;j<3;j++){if (s[i][j]=='A'){fir.ax = i;fir.ay = j;}else if (s[i][j]=='B'){fir.bx = i;fir.by = j;}else if (s[i][j]==' '){fir.kx = i;fir.ky = j;}}cout<<bfs(fir)<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的[蓝桥杯2016初赛]卡片换位-bfs的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。