題意：
? ? ? 給你一個地圖，有的地方能走，有的地方不能走，然后給你一條蛇，問你這條蛇的頭部走到1，1的位置的最少步數，注意，和貪吃蛇不太一樣，就是蛇咬到自己身體的那個地方，具體怎么不一樣自己模擬下那個數據就明白了。


思路：
? ? ? 敲了挺長時間的，可能是剛過完年回來半個月沒寫代碼手有點生了，一開始有個SB的想法就是我感覺只標記蛇的頭部和尾部就行了，索然在敲之前已經動搖了，但是還是硬著頭皮敲了一個代碼，果斷WA了，然后就是敲正確的方式（估計我的也不是標準的，以為我是5000MS g++過的，直接踩線過的節奏，里面自己平感覺優化了一些），我是mark[x][y][v],x,y是蛇頭坐標，v是蛇身體的狀態，狀態壓縮（4進制的（其實感覺三進制也行，然后在加個蛇的方向，沒嘗試去寫，狀態少點，沒準會快點））思路就是首先從蛇頭后的第一個開始相對于蛇頭的位置，上下左右，然后是蛇頭后第二個相對于第一個的位置，上下左右，這樣就可以用 x y v三個int來表示條蛇的位置和狀態了，我的跑了5000MS，其實我感覺還有一個地方可以優化，就是我判斷的時候浪費了l（蛇長度）的時間，其實我們可以空間換時間，我覺得可以在每個結構體里面開個二維的map來標記當前的蛇的身體（為了判斷撞到自己身體用的）更新這個O(1)的時間，至于蛇狀態之間的轉換，可以直接用取余的方法把最高位去掉，然后*4，然后再把第一位填上，這個操作的時間復雜度也是O(1)的，對于我的總時間復雜度的話T的話優化后是大約 T/L的，這個是理論值，具體的我也沒去敲，我是這么想的，有興趣的可以敲下試試，最好就是用三個方向，然后在空間換時間去優化，估計能快點。但是想刷排名還是用A*吧，雖然我現在不會。


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


#define N 20 + 1
#define M 16384


using namespace std;


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


typedef struct
{
? ? int x ,y ,v ,t;
}P;


P tou ,xin;
NODE S[10];
int map[N][N] ,n ,m ,l;
int mark[N][N][M];
int dir[4][2] = {-1 ,0 ,1 ,0 ,0 ,-1 ,0 ,1};


int GetXinV()//得到xin.v并且判斷是否撞到自己
{
? ? int tmp = 4;
? ? int x = tou.x ,y = tou.y;
? ? for(int i = 2 ;i <= l ;i ++)
? ? {
? ? ? ? int now = tou.v % tmp / (tmp / 4);
? ? ? ? if(i <= l - 1) xin.v += now * tmp;
? ? ? ? x = x + dir[now][0];
? ? ? ? y = y + dir[now][1];
? ? ? ? if(x == xin.x && y == xin.y)
? ? ? ? return 0;
? ? ? ? tmp *= 4;
? ? }
? ? return 1;
}


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


int BFS()
{
? ? memset(mark ,0 ,sizeof(mark));
? ? mark[xin.x][xin.y][xin.v] = 1;
? ? queue<P>q;
? ? q.push(xin);
? ? while(!q.empty())
? ? {
? ? ? ? tou = q.front();
? ? ? ? q.pop();
? ? ? ? //printf("%d %d %d**\n" ,tou.x ,tou.y ,tou.v);
? ? ? ? if(tou.x == 1 && tou.y == 1)
? ? ? ? return tou.t;
? ? ? ? for(int i = 0 ;i < 4 ;i ++)
? ? ? ? {
? ? ? ? ? ? xin.x = tou.x + dir[i][0];
? ? ? ? ? ? xin.y = tou.y + dir[i][1];
? ? ? ? ? ? xin.t = tou.t + 1;
? ? ? ? ? ? xin.v = i ^ 1;
? ? ? ? ? ? if(!ok(xin.x ,xin.y)) continue;
? ? ? ? ? ? if(GetXinV())
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(!mark[xin.x][xin.y][xin.v])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? mark[xin.x][xin.y][xin.v] = 1;
? ? ? ? ? ? ? ? ? ? if(xin.x == 1 && xin.y == 1)
? ? ? ? ? ? ? ? ? ? return xin.t;
? ? ? ? ? ? ? ? ? ? q.push(xin);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return -1;
}


int main ()
{
? ? int i ,x ,y ,cas = 1;
? ? while(~scanf("%d %d %d" ,&n ,&m ,&l) && n + m + l)
? ? {
? ? ? ? for(i = 1 ;i <= l ;i ++)
? ? ? ? scanf("%d %d" ,&S[i].x ,&S[i].y);
? ? ? ? memset(map ,0 ,sizeof(map));
? ? ? ? scanf("%d" ,&i);
? ? ? ? while(i--)
? ? ? ? {
? ? ? ? ? ? scanf("%d %d" ,&x ,&y);
? ? ? ? ? ? map[x][y] = 1;
? ? ? ? }
? ? ? ? xin.x = S[1].x ,xin.y = S[1].y;
? ? ? ? xin.t = xin.v = 0;
? ? ? ? int tmp = 1;
? ? ? ? for(i = 2 ;i <= l ;i ++)
? ? ? ? {
? ? ? ? ? ? int now;
? ? ? ? ? ? if(S[i].x - S[i-1].x == 1) now = 1;
? ? ? ? ? ? else if(S[i].x - S[i-1].x == -1) now = 0;
? ? ? ? ? ? else if(S[i].y - S[i-1].y == 1) now = 3;
? ? ? ? ? ? else now = 2;
? ? ? ? ? ? xin.v += now * tmp;
? ? ? ? ? ? tmp *= 4;
? ? ? ? }
? ? ? ? printf("Case %d: %d\n" ,cas ++ ,BFS());
? ? }
}

總結

以上是生活随笔為你收集整理的POJ1324贪吃蛇（状态压缩广搜）的全部內容，希望文章能夠幫你解決所遇到的問題。

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