HDU1429 胜利大逃亡(续) BFS +简单状压

把手中持有的钥匙状态状压一下即可，然后vis访问标记的时候，开个三维，多一维即为当前持有钥匙状态，这样就能祛除重复标记困难走点的问题，跟网络赛那题很像，网络赛的更难点，这个简单点

int n,m,t;

int sx,sy,ex,ey;

char mp[20 + 55][20 + 55];

bool vis[20 + 5][20 + 5][(1<<10) + 5];

int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};

struct Node {
	int now;//现在钥匙状态
	int x,y;
	int step;
	friend bool operator<(Node aa,Node bb) {
		return aa.step > bb.step;
	}
};

void init() {
	memset(vis,false,sizeof(vis));
}

bool input() {
    while(cin>>n>>m>>t) {
		for(int i=0;i
  
    q;
	Node ss,ee;
	ss.x = x,ss.y = y,ss.step = 0,ss.now = 0;
	q.push(ss);
	vis[ss.x][ss.y][0] = true;
	while(!q.empty()) {
		ss = q.front();
		q.pop();
		if(ss.step >= t)continue;
		if(ss.x == ex && ss.y == ey) {
			ans = min(ans,ss.step);
			break;
		}
		for(int i=0;i<4;i++) {
			int dx = ss.x + dir[i][0];
			int dy = ss.y + dir[i][1];
			if(dx < 0 || dx >= n || dy < 0 || dy >= m)continue;
			if(mp[dx][dy] == '*')continue;
			if(vis[dx][dy][ss.now])continue;
			ee.now = ss.now;
			if(mp[dx][dy] >= 'A' && mp[dx][dy] <= 'J') {/*遇到门*/
				int tmp = mp[dx][dy] - 'A';
				if((ss.now&(1<
   
    = 'a' && mp[dx][dy] <= 'z') {/*遇到钥匙*/ int tmp = mp[dx][dy] - 'a'; ee.now |= (1<
    
     = t)puts("-1"); else cout<