Codeforces 225D Snake 位運算hash + bfs

題意：有一只在n*m（1<=n，m<=15）的迷宮內，蛇頭為1，身長<=9，@為蘋果，#為牆，問最小幾步能吃到蘋果。吃不到輸出-1。
題解：hash存儲兩個相鄰蛇身的關系上下左右四種狀態用兩位二進制表示，dis[ i ][ j ][ t ] 表示蛇頭在i j 位置蛇身狀態為 t 的時候的最小步數，然後bfs即可。

Sure原創，轉載請注明出處。
[cpp] 
#includ ((a) > (b) ? (a) : (b)) 
using namespace std; 
const int maxn = 20; 
const int maxt = 1 << 17; 
const int move[4][2] = {{-1,0},{0,1},{1,0},{0,-1}}; 
struct ddd 
{ 
    int x,y,s; 
}; 
char map[maxn][maxn]; 
int st[2][maxn >> 1],dis[maxn][maxn][maxt]; 
bool vis[maxn][maxn][maxt]; 
queue <ddd> Q; 
int m,n,len,edx,edy; 
 
int hash() 
{ 
    int res = 0; 
    for(int i=len-1;i>0;i--) 
    { 
        for(int j=0;j<4;j++) 
        { 
            if(st[0][i-1] + move[j][0] == st[0][i] && st[1][i-1] + move[j][1] == st[1][i]) 
            { 
                res <<= 2; 
                res |= j; 
            } 
        } 
    } 
    return res; 
} 
 
bool judge(int x,int y,int px,int py,int ss) 
{ 
    if(x >= 0 && y >= 0 && x < m && y < n && map[x][y] != '#') 
    { 
        int ppx = px + move[ss&3][0]; 
        int ppy = py + move[ss&3][1]; 
        if(ppx == x && ppy == y) return false; 
        st[0][0] = x; 
        st[1][0] = y; 
        st[0][1] = px; 
        st[1][1] = py; 
        for(int i=2;i<len;i++) 
        { 
            int d = ss & 3; 
            px += move[d][0]; 
            py += move[d][1]; 
            if(px == x && py == y) return false; 
            st[0][i] = px; 
            st[1][i] = py; 
            ss >>= 2; 
        } 
        return true; 
    } 
    return false; 
} 
 
void read() 
{ 
    memset(vis,false,sizeof(vis)); 
    len = 0; 
    for(int i=0;i<m;i++) 
    { 
        scanf("%s",map[i]); 
        for(int j=0;j<n;j++) 
        { 
            if(map[i][j] >= '1' && map[i][j] <= '9') 
            { 
                int tmp = map[i][j] - '1'; 
                st[0][tmp] = i; 
                st[1][tmp] = j; 
                len = MAX(len , tmp+1); 
            } 
            if(map[i][j] == '@') 
            { 
                edx = i; 
                edy = j; 
            } 
        } 
    } 
    return; 
} 
 
int bfs() 
{ 
    while(!Q.empty()) Q.pop(); 
    int key = hash(); 
    vis[st[0][0]][st[1][0]][key] = true; 
    dis[st[0][0]][st[1][0]][key] = 0; 
    ddd cur,tmp; 
    tmp.x = st[0][0]; 
    tmp.y = st[1][0]; 
    tmp.s = key; 
    Q.push(tmp); 
    while(!Q.empty()) 
    { 
        cur = Q.front(); 
        Q.pop(); 
        if(cur.x == edx && cur.y == edy) 
        { 
            return dis[edx][edy][cur.s]; 
        } 
        for(int i=0;i<4;i++) 
        { 
            int tx = cur.x + move[i][0]; 
            int ty = cur.y + move[i][1]; 
            if(judge(tx , ty , cur.x , cur.y , cur.s)) 
            { 
                tmp.x = tx; 
                tmp.y = ty; 
                tmp.s = hash(); 
                if(vis[tx][ty][tmp.s] == false) 
                { 
                    vis[tx][ty][tmp.s] = true; 
                    dis[tx][ty][tmp.s] = dis[cur.x][cur.y][cur.s] + 1; 
                    Q.push(tmp); 
                } 
            } 
        } 
    } 
    return -1; 
} 
 
int main() 
{ 
    while(~scanf("%d %d",&m,&n)) 
    { 
        read(); 
        printf("%d\n",bfs()); 
    } 
    return 0; 
}