TOJ 432
題目
https://toj.tfcis.org/oj/pro/432/
有一個 $N \times M$ 的棋盤，在這個棋盤上有 $F$ 個著火的點 $(x_i, y_i)$ 以及一個門 $(u, v)$
現在有個人在 $(x_{me}, y_{me})$ 的位置，每次可以上下左右選擇一個移動一格，請問這個人是否能在不碰到火的情況下走到門的位置
想法
我們可以嘗試從人所在的位置開始，每次走一步，每一個方向都走過，直到找到門或是把全部可行的格子走過，那麼就會知道答案了
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
|
#include<iostream>
using namespace std;
int n, m, f, arr[1005][1005], que[1000005][2];
int start_x, start_y, end_x, end_y, cur_x, cur_y, nx, ny;
bool vis[1005][1005], ans=false;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
void BFS(){
que[0][0] = start_x;
que[0][1] = start_y;
vis[start_x][start_y] = true;
for(int i=0, j=1 ; i<j ; i++){
cur_x = que[i][0];
cur_y = que[i][1];
if(cur_x == end_x && cur_y == end_y){
ans=true;
break;
}
for(int k=0 ; k<4 ; k++){
nx = cur_x + dx[k];
ny = cur_y + dy[k];
if(nx > n || nx <= 0 || ny <= 0 || ny > m) continue;
if(!vis[nx][ny] && arr[nx][ny] != 1){
vis[nx][ny] = true;
que[j][0] = nx;
que[j][1] = ny;
j++;
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1 ; i<=n ; i++){
for(int j=1 ; j<=m ; j++){
arr[i][j] = 0;
vis[i][j] = false;
}
}
cin>>start_x>>start_y>>end_x>>end_y;
cin>>f;
for(int i=0, x, y ; i<f ; i++){
cin>>x>>y;
arr[x][y] = 1;
}
BFS();
if(ans){
cout<<"Cool!\n";
}
else{
cout<<"Harakiri!\n";
}
return 0;
}
|
時間複雜度分析
輸入時間複雜度為 $O(nm + f)$
BFS 時間複雜度為 狀態數 $\times$ 操作數量 $= (nm) \times 4$，計為 $O(nm)$
總時間複雜度為 $O(2nm + f)$