HDU1429 勝利大逃亡(續) BFS +簡單狀壓

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<