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;  
}

补充：软件开发 , C++ ,