Koios1143的筆記

TOJ 449

發表於 分類於

TOJ 449

題目

https://toj.tfcis.org/oj/pro/449/

給一張迷宮的地圖，其中包含障礙物、門、鑰匙、起點、終點

每個門都需要有相對應的鑰匙才可以打開，而一把鑰匙可以無限次使用
地圖可能有多終點

每次可以選擇上下左右一個方向前進，請問最少需要花多少的步驟走到終點

想法

因為要找的是最少步驟，因此可以想到用 BFS 來解

現在所擁有的鑰匙會影響到未來發展，因此每次需要考慮到當前有哪些鑰匙

因此我們的狀態就包含了 當前座標 以及 擁有的鑰匙

我們可以使用 bit 的方式去記錄每個鑰匙是否已經擁有

每次走到門就檢查該 bit 是否是 1

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//By Koios1143
#include<iostream>
using namespace std;
int n, m, ans, start_x, start_y;
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
int key_num[26], dis[105][105][50];
int que[10010][3];
string keys="RGBY";
char arr[105][105];
bool vis[105][105][50];

int BFS(){
	que[0][0] = start_x;
	que[0][1] = start_y;
	que[0][2] = 0;
	dis[start_x][start_y][0] = 0;
	vis[start_x][start_y][0] = true;
	
	for(int head=0, tail=1, x, y, key, nx, ny, nkey ; head<tail ; head++){
		x = que[head][0];
		y = que[head][1];
		key = que[head][2];
		
		if(arr[x][y] == 'X'){
			return dis[x][y][key];
		}
		
		for(int i=0 ; i<4 ; i++){
			nx = x + dx[i];
			ny = y + dy[i];
			nkey = key;
			if(nx<0 || nx>=n || ny<0 || ny>=m || arr[nx][ny] == '#') continue;
			
			if(arr[nx][ny] == 'R' || arr[nx][ny] == 'G' || arr[nx][ny] == 'B' || arr[nx][ny] == 'Y'){
				// 下一個點是門，檢查該 bit 是否為 1
				if((key & (1<<key_num[arr[nx][ny]-'A'])) == 0){
					continue;
				}
			}
			else if(arr[nx][ny] == 'r' || arr[nx][ny] == 'g' || arr[nx][ny] == 'b' || arr[nx][ny] == 'y'){
				// 下個點是鑰匙，更新擁有的鑰匙
				nkey = (key | (1<<key_num[arr[nx][ny]-'a']));
			}
			if(!vis[nx][ny][nkey]){
				vis[nx][ny][nkey] = true;
				que[tail][0] = nx;
				que[tail][1] = ny;
				que[tail][2] = nkey;
				dis[nx][ny][nkey] = dis[x][y][key] + 1;
				tail++;
			}
		}
	}
	return -1;
}

int main(){
	// 把鑰匙對應一個數字
	for(int i=0 ; i<keys.size() ; i++){
		key_num[keys[i]-'A'] = i;
	}
	while(cin>>n>>m){
		for(int i=0 ; i<n ; i++){
			for(int j=0 ; j<m ; j++){
				for(int k=0 ; k<50 ; k++){
					vis[i][j][k] = false;
				}
				cin>>arr[i][j];
				if(arr[i][j] == '*'){
					start_x = i;
					start_y = j;
				}
			}
		}
		ans = BFS();
		if(ans == -1){
			cout<<"The poor student is trapped!\n";
		}
		else{
			cout<<"Escape possible in "<<ans<<" steps.\n";
		}
	}
	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(nm)$

每筆測資 BFS 時間複雜度為 狀態數 $\times$ 操作的數量 $= (2^4nm) \times(4)$ 大約為 $O(nm)$

每筆測資總時間複雜度為 $O(nm)$