HDU 1429 勝利大逃亡(續) (BFS + 狀態壓縮)

好好的一道題，又被我搞廢了

中文題目題意就不用說了。把鑰匙的有無情況狀態壓縮：01代表有1號鑰匙，10代表有2號鑰匙，11代表有1號和2號鑰匙...................................................................

思維錯在兩點，弄了一上午：

1. 判斷點是否入隊，除去最前提的條件，還有就是該點的狀態是否更新了（即為是否拿了某把鑰匙），更新後的狀態未出現過就能入隊............一開始沒有考慮狀態問題直接入隊，會有在兩個點中走來走去的re情況。

2.同樣的鑰匙可能有多把，一開始寫法是碰到已經拿過的鑰匙，該點不入隊，這樣就會出現問題：如果剛好到達終點的這條路上有同樣的鑰匙，那就變成不能到達了。

所以重復的鑰匙不需要多考慮。

#include <cstdio>   
#include <iostream>   
#include <cmath>   
#include <cstring>   
#include <algorithm>   
using namespace std;  
int n,m,head,tail,T;  
char map[33][33];  
int dp[33][33][1 << 10];  
int dirx[] = {1,-1,0,0};  
int diry[] = {0,0,1,-1};  
struct node {  
    int x,y;  
    int buff;  
} q[1111111],st,end;  
  
void init() {  
    memset(dp,-1,sizeof(dp));  
    head = 0;  
    tail = 0;  
}  
  
bool go(int x,int y) {  
    if(x < 0 || x >= n || y < 0 || y >= m) return false;  
    if(map[x][y] == '*') return false;  
    return true;  
}  
int bfs() {  
    q[head++] = st;  
    dp[st.x][st.y][st.buff] = 0;  
    while(head != tail) {  
        node t = q[tail++];  
        node tt ;  
        if(t.x == end.x && t.y == end.y) {  
            if(T > dp[t.x][t.y][t.buff]) return dp[t.x][t.y][t.buff];  
            else return -1;  
        }  
        if(dp[t.x][t.y][t.buff] >= T) return -1;  
        for(int i=0; i<4; i++) {  
            tt.x = t.x + dirx[i];  
            tt.y = t.y + diry[i];  
            tt.buff = t.buff;  
            if(go(tt.x,tt.y)) {  
                if(map[tt.x][tt.y] >='A' && map[tt.x][tt.y] <='J') {  
                    int move = map[tt.x][tt.y] - 'A';  
                    if(((t.buff >> move) &  1) == 0) continue;  
  
                } else if(map[tt.x][tt.y] >= 'a' && map[tt.x][tt.y] <='j') {  
                    int move = map[tt.x][tt.y] - 'a';  
                    // if((t.buff >> move) & 1) continue;  //此處不應該考慮的    
                    tt.buff = t.buff | (1 << move);  
                }  
                if(dp[tt.x][tt.y][tt.buff] == -1) {  
                    dp[tt.x][tt.y][tt.buff] = dp[t.x][t.y][t.buff] + 1;  
                    q[head++] = tt;  
                }  
            }  
        }  
    }  
    return -1;  
}  
int main() {  
    while(scanf("%d%d%d",&n,&m,&T) != EOF) {  
        init();  
        for(int i=0; i<n; i++) scanf("%s",map[i]);  
        for(int i=0; i<n; i++)  
            for(int j=0; j<m; j++) {  
                if(map[i][j] == '@') {  
                    st.x = i;  
                    st.y = j;  
                    st.buff = 0;  
                }  
                if(map[i][j] == '^') {  
                    end.x = i;  
                    end.y = j;  
                    end.buff = 0;  
                }  
            }  
        printf("%d\n",bfs());  
    }  
    return 0;  
}