Untitled
unknown
plain_text
2 years ago
5.4 kB
6
Indexable
Never
//想法是有兩個 bfs 一個是火焰的 一個是人的逃跑路線 同樣也有兩個 visited 來記錄 逃跑的路線每次跑完一次時間 now(time)++ 然後為了 配合時間的變化 用time 記錄人跑時這個點是在哪一個時間點 直接在maze 利用數字紀錄現在火燒到哪 然後用 distance 紀錄距離// #include <cmath> #include <cstdio> #include <vector> #include <deque> #include <iostream> #include <algorithm> #include <ctype.h> using namespace std; int fire_rampage(vector<vector<char>> &maze, int x, int y, int n, int m, vector<vector<int>> &visited) //火焰可燃燒的地方 { if (x < n && x >= 0 && y < m && y >= 0 && visited[x][y] == 0 && maze[x][y] != '*' && maze[x][y] != 'E') return 1; else return 0; } int is_safe(vector<vector<char>> &maze, int x, int y, int n, int m, vector<vector<int>> &visited) // 人可逃離的地方 { if (!isdigit(maze[x][y])) { if (x < n && x >= 0 && y < m && y >= 0 && visited[x][y] == 0 && maze[x][y] != '*') return 1; else return 0; } else return 0; } int Time(vector<vector<char>> &maze, int burn_x, int burn_y, int x, int y, int end_x, int end_y, int now, int notice_time, vector<vector<int>> &visited, vector<vector<int>> visited_2, vector<vector<int>> distance, int H, int W) { vector<deque<int>> queue(2); vector<deque<int>> queue_2(2); vector<vector<int>> time(H, vector<int>(W)); vector<int> dr {-1, 1, 0, 0 ,1 ,1 ,-1 ,-1}, dc {0, 0, -1, 1 ,1 ,-1 ,1,-1}; //方向 前四個是上下左右,後面是右上左下.... time[x][y] = notice_time; bool flag = false; int max; queue[0].push_front(x), queue[1].push_front(y); queue_2[0].push_front(burn_x), queue_2[1].push_front(burn_y); visited[x][y] = 1; visited_2[burn_x][burn_y] = 1; while (!(queue[0].empty() && queue[1].empty())) { if(flag == true) break; while (!(queue_2[0].empty() && queue_2[1].empty())) // fire bfs { auto b_x = queue_2[0].front(); auto b_y = queue_2[1].front(); if (maze[b_x][b_y] == now + 48) // 同樣也是記錄時間符合那個點 { for (int i = 0; i < 4; i++) { int x = b_x +dr[i], y = b_y +dc[i]; if (fire_rampage(maze, x, y, H, W, visited_2)) { maze[x][y] = maze[b_x][b_y] + 1; queue_2[0].push_back(x); queue_2[1].push_back(y); visited_2[x][y] = 1; } } queue_2[0].pop_front(); queue_2[1].pop_front(); } else break; } while (!(queue[0].empty() && queue[1].empty())) // human bfs { if (now >= notice_time) // 時間大於等於察覺時間 { auto from_x = queue[0].front(); auto from_y = queue[1].front(); if (time[from_x][from_y] == now) //確認這個點在正確時間點 { for(int i = 0; i < 8;i++) { int x = from_x + dr[i] , y = from_y + dc[i]; if (is_safe(maze, x, y, H, W, visited)) { visited[x][y] = 1; distance[x][y] = distance[from_x][from_y] + 1; time[x][y] = time[from_x][from_y] + 1; if (x == end_x && y == end_y) { flag = true; max = distance[x][y]; break; } queue[0].push_back(x), queue[1].push_back(y); } } queue[0].pop_front(); queue[1].pop_front(); } else break; } else break; } now++; } if (flag) return max; else return 0; } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int n, m; cin >> n >> m; vector<vector<char>> maze(n, vector<char>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> maze[i][j]; } } int first_burn_x, first_burn_y; int initi_x, initi_y; int end_x, end_y; int notice_x, notice_y; int notice_time; cin >> first_burn_x >> first_burn_y; cin >> notice_time; cin >> notice_x >> notice_y >> end_x >> end_y; maze[first_burn_x][first_burn_y] = '1'; maze[notice_x][notice_y] = 'S'; maze[end_x][end_y] = 'E'; vector<vector<int>> visited(n, vector<int>(m)); vector<vector<int>> visited_2(n, vector<int>(m)); vector<vector<int>> distance(n, vector<int>(m)); int T = Time(maze, first_burn_x, first_burn_y, notice_x, notice_y, end_x, end_y, 1, notice_time, visited, visited_2, distance, n, m); if (T == 0) cout << "Help!"; else cout << T; return 0; }