題意：
? ? ? 講的是一個游戲，就是在一個平面上滾動一個1*1*2的長方體的游戲，在本題里面的游戲規則是這樣的：
（1）
? ? ?一開始給你箱子的狀態，可能是橫著也可能是豎著。
（2）
? ? ?每一次可以滾動箱子，但是每次滾動到的位置（1個或者2個）都必須不能是空的。
（3）
? ? ?有的位置只能經得起箱子一半的重量，有的能經得起真個箱子的重量，經得起一半的格子意思就是不能在當前的這個格子上吧箱子豎起來。
（4）然后問從起始狀態到掉到終點給的洞里面的最小步數，掉到洞里面的時候必須是豎直掉下去的。





思路：
? ? ? 比較明顯可以用搜索來做，但是這個題目的關鍵點是如何標記狀態，我的做法是對于每一個點都有五個狀態，就是另一個點相對于這個點的位置，可以是東南西北，還有正上方
，標記的時候是這樣的依靠五個狀態，搜索的時候為了簡化代碼我寫的是3個狀態的，因為有一些等效狀態，我們只要搜索其中的一個就行了，但是如果你愿意把所有的狀態都寫出來，那么一共是5種，每種有四個方向的走法一共是5*4種選擇，這樣代碼量估計比較大，如果是相等狀態只進一個的話可以達到3*4種選擇，但是這樣的話要注意就是在mark的時候的一些細節，別的沒啥的就是簡單廣搜，姿勢好點應該沒啥大問題，具體細節可以看下面代碼。


#include<queue>
#include<stdio.h>
#include<string.h>


using namespace std;


typedef struct
{
? ? int x ,y ,t ,k;
}NODE;


NODE xin ,tou;
int map[505][505] ,n ,m;
int mark[505][505][5];
int ex ,ey;


bool ok(int x ,int y ,int k)
{
? ? return x >= 1 && x <= n && y >= 1 && y <= m && map[x][y] && !mark[x][y][k];
}


int BFS()
{
? ? queue<NODE>q;
? ? q.push(xin);
? ? memset(mark ,0 ,sizeof(mark));
? ? mark[xin.x][xin.y][xin.k] = 1;
? ? NODE X1 ,X2;
? ? while(!q.empty())
? ? {
? ? ? ? tou = q.front();
? ? ? ? q.pop();
? ? ? ? //printf("%d %d %d %d**\n" ,tou.x ,tou.y ,tou.k ,tou.t);
? ? ? ? if(!tou.k && tou.x == ex && tou.y == ey)
? ? ? ? return tou.t;
? ? ? ? if(tou.k == 0)
? ? ? ? {
? ? ? ? ? ? //上
? ? ? ? ? ? X1.x = tou.x - 1 ,X1.y = tou.y ,X1.k = 1;
? ? ? ? ? ? X2.x = tou.x - 2 ,X2.y = tou.y ,X2.k = 3;
? ? ? ? ? ? if(ok(X1.x ,X1.y ,X1.k) && ok(X2.x ,X2.y ,X2.k))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? mark[X1.x][X1.y][X1.k] = mark[X2.x][X2.y][X2.k] = 1;
? ? ? ? ? ? ? ? X1.t = tou.t + 1;
? ? ? ? ? ? ? ? q.push(X1);
? ? ? ? ? ? }


? ? ? ? ? ? //下
? ? ? ? ? ? X1.x = tou.x + 1 ,X1.y = tou.y ,X1.k = 3;
? ? ? ? ? ? X2.x = tou.x + 2 ,X2.y = tou.y ,X2.k = 1;
? ? ? ? ? ? if(ok(X1.x ,X1.y ,X1.k) && ok(X2.x ,X2.y ,X2.k))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? mark[X1.x][X1.y][X1.k] = mark[X2.x][X2.y][X2.k] = 1;
? ? ? ? ? ? ? ? X2.t = tou.t + 1;
? ? ? ? ? ? ? ? q.push(X2);
? ? ? ? ? ? }


? ? ? ? ? ? //左
? ? ? ? ? ? X1.x = tou.x ,X1.y = tou.y - 1 ,X1.k = 4;
? ? ? ? ? ? X2.x = tou.x ,X2.y = tou.y - 2 ,X2.k = 2;
? ? ? ? ? ? if(ok(X1.x ,X1.y ,X1.k) && ok(X2.x ,X2.y ,X2.k))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? mark[X1.x][X1.y][X1.k] = mark[X2.x][X2.y][X2.k] = 1;
? ? ? ? ? ? ? ? X1.t = tou.t + 1;
? ? ? ? ? ? ? ? q.push(X1);
? ? ? ? ? ? }


? ? ? ? ? ? //右
? ? ? ? ? ? X1.x = tou.x ,X1.y = tou.y + 1 ,X1.k = 2;
? ? ? ? ? ? X2.x = tou.x ,X2.y = tou.y + 2 ,X2.k = 4;
? ? ? ? ? ? if(ok(X1.x ,X1.y ,X1.k) && ok(X2.x ,X2.y ,X2.k))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? mark[X1.x][X1.y][X1.k] = mark[X2.x][X2.y][X2.k] = 1;
? ? ? ? ? ? ? ? X2.t = tou.t + 1;
? ? ? ? ? ? ? ? q.push(X2);
? ? ? ? ? ? }


? ? ? ? }
? ? ? ? else if(tou.k == 1)
? ? ? ? {
? ? ? ? ? ? //上
? ? ? ? ? ? X1.x = tou.x - 2 ,X1.y = tou.y ,X1.k = 0;
? ? ? ? ? ? if(ok(X1.x ,X1.y ,X1.k) && map[X1.x][X1.y] == 1)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? X1.t = tou.t + 1;
? ? ? ? ? ? ? ? mark[X1.x][X1.y][X1.k] = 1;
? ? ? ? ? ? ? ? q.push(X1);
? ? ? ? ? ? }


? ? ? ? ? ? //下
? ? ? ? ? ? X1.x = tou.x + 1 ,X1.y = tou.y ,X1.k = 0;
? ? ? ? ? ? if(ok(X1.x ,X1.y ,X1.k) && map[X1.x][X1.y] == 1)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? X1.t = tou.t + 1;
? ? ? ? ? ? ? ? mark[X1.x][X1.y][X1.k] = 1;
? ? ? ? ? ? ? ? q.push(X1);
? ? ? ? ? ? }


? ? ? ? ? ? //左
? ? ? ? ? ? X1.x = tou.x ,X1.y = tou.y - 1 ,X1.k = 1;
? ? ? ? ? ? X2.x = tou.x - 1 ,X2.y = tou.y - 1 ,X2.k = 3;
? ? ? ? ? ? if(ok(X1.x ,X1.y ,X1.k) && ok(X2.x ,X2.y ,X2.k))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? mark[X1.x][X1.y][X1.k] = mark[X2.x][X2.y][X2.k] = 1;
? ? ? ? ? ? ? ? X1.t = tou.t + 1;
? ? ? ? ? ? ? ? q.push(X1);
? ? ? ? ? ? }


? ? ? ? ? ? //右
? ? ? ? ? ? X1.x = tou.x ,X1.y = tou.y + 1 ,X1.k = 1;
? ? ? ? ? ? X2.x = tou.x - 1 ,X2.y = tou.y + 1 ,X2.k = 3;
? ? ? ? ? ? if(ok(X1.x ,X1.y ,X1.k) && ok(X2.x ,X2.y ,X2.k))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? mark[X1.x][X1.y][X1.k] = mark[X2.x][X2.y][X2.k] = 1;
? ? ? ? ? ? ? ? X1.t = tou.t + 1;
? ? ? ? ? ? ? ? q.push(X1);
? ? ? ? ? ? }


? ? ? ? }
? ? ? ? else if(tou.k == 4)
? ? ? ? {
? ? ? ? ? ? //上
? ? ? ? ? ? X1.x = tou.x - 1 ,X1.y = tou.y ,X1.k = 4;
? ? ? ? ? ? X2.x = tou.x - 1 ,X2.y = tou.y - 1 ,X2.k = 2;
? ? ? ? ? ? if(ok(X1.x ,X1.y ,X1.k) && ok(X2.x ,X2.y ,X2.k))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? mark[X1.x][X1.y][X1.k] = mark[X2.x][X2.y][X2.k] = 1;
? ? ? ? ? ? ? ? X1.t = tou.t + 1;
? ? ? ? ? ? ? ? q.push(X1);
? ? ? ? ? ? }
? ? ? ? ? ? //下
? ? ? ? ? ? X1.x = tou.x + 1 ,X1.y = tou.y ,X1.k = 4;
? ? ? ? ? ? X2.x = tou.x + 1 ,X2.y = tou.y - 1 ,X2.k = 2;
? ? ? ? ? ? if(ok(X1.x ,X1.y ,X1.k) && ok(X2.x ,X2.y ,X2.k))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? mark[X1.x][X1.y][X1.k] = mark[X2.x][X2.y][X2.k] = 1;
? ? ? ? ? ? ? ? X1.t = tou.t + 1;
? ? ? ? ? ? ? ? q.push(X1);
? ? ? ? ? ? }
? ? ? ? ? ? //左
? ? ? ? ? ? X1.x = tou.x ,X1.y = tou.y - 2 ,X1.k = 0;
? ? ? ? ? ? if(ok(X1.x ,X1.y ,X1.k) && map[X1.x][X1.y] == 1)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? X1.t = tou.t + 1;
? ? ? ? ? ? ? ? mark[X1.x][X1.y][X1.k] = 1;
? ? ? ? ? ? ? ? q.push(X1);
? ? ? ? ? ? }


? ? ? ? ? ? //右
? ? ? ? ? ? X1.x = tou.x ,X1.y = tou.y + 1 ,X1.k = 0;
? ? ? ? ? ? if(ok(X1.x ,X1.y ,X1.k) && map[X1.x][X1.y] == 1)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? X1.t = tou.t + 1;
? ? ? ? ? ? ? ? mark[X1.x][X1.y][X1.k] = 1;
? ? ? ? ? ? ? ? q.push(X1);
? ? ? ? ? ? }


? ? ? ? }
? ? }
? ? return -1;
}


int main ()
{
? ? char str[505];
? ? int sx1 ,sx2 ,sy1 ,sy2 ,s;
? ? while(~scanf("%d %d" ,&n ,&m) && n + m)
? ? {
? ? ? ? s = 0;
? ? ? ? for(int i = 1 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? scanf("%s" ,str);
? ? ? ? ? ? for(int j = 1 ;j <= m ;j ++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(str[j-1] == 'X')
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? s ++;
? ? ? ? ? ? ? ? ? ? if(s == 1) sx1 = i ,sy1 = j;
? ? ? ? ? ? ? ? ? ? else sx2 = i ,sy2 = j;
? ? ? ? ? ? ? ? ? ? map[i][j] = 1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else if(str[j-1] == 'O')
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ex = i ,ey = j;
? ? ? ? ? ? ? ? ? ? map[i][j] = 1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else if(str[j-1] == 'E') map[i][j] = 2;
? ? ? ? ? ? ? ? else if(str[j-1] == '#') map[i][j] = 0;
? ? ? ? ? ? ? ? else map[i][j] = 1;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if(s == 1) xin.x = sx1 ,xin.y = sy1 ,xin.k = 0 ,xin.t = 0;
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? if(sx1 == sx2) xin.x = sx2 ,xin.y = sy2 ,xin.k = 4 ,xin.t = 0;
? ? ? ? ? ? else xin.x = xin.x = sx2 ,xin.y = sy2 ,xin.k = 1 ,xin.t = 0;
? ? ? ? }
? ? ? ? int ans = BFS();
? ? ? ? ans == -1 ? printf("Impossible\n") : printf("%d\n" ,ans);
? ? }
? ? return 0;
}

總結

以上是生活随笔為你收集整理的POJ3322滚箱子游戏（不错）的全部內容，希望文章能夠幫你解決所遇到的問題。

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