做了熱身賽http://blog.csdn.net/u013081425/article/details/21740001 之後發現這道題好水，之前怎麼沒刷到呢。。
同樣標記數組增加一維，標記到某一點時他擁有鑰匙的狀態，因為有10種鑰匙，所以mark[][][1<<10+10]來標記每到一點的狀態。
#include#include #include #include using namespace std; int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} }; struct node { int x,y; int step; int sta; }p[410]; queue que; char map[30][30]; int n,m,t; int sx,sy; int mark[30][30][1<<10+10]; void bfs() { memset(mark,0,sizeof(mark)); while(!que.empty()) que.pop(); que.push((struct node) {sx,sy,0,0}); mark[sx][sy][0] = 1; while(!que.empty()) { struct node u = que.front(); que.pop(); if(u.step >= t) { printf(-1 ); return; } if(map[u.x][u.y] == '^') { printf(%d ,u.step); return; } for(int d = 0; d <= 3; d++) { int x = u.x+dir[d][0]; int y = u.y+dir[d][1]; if(x < 1 || x > n || y < 1 || y > m) continue; int sta = u.sta; int add; if(map[x][y] == '.' || map[x][y] == '@' || map[x][y] == '^') { if(!mark[x][y][sta]) { que.push((struct node){x,y,u.step+1,sta}); mark[x][y][sta] = 1; } } else if(map[x][y] >= 'a' && map[x][y] <= 'j') { add = map[x][y]-'a'; if((sta & (1<= 'A' && map[x][y] <= 'J') { add = map[x][y] - 'A'; if( (sta & (1<
