Untitled
unknown
plain_text
2 years ago
5.2 kB
2
Indexable
Never
#include <cmath> #include <cstdio> #include <vector> #include <deque> #include <iostream> #include <algorithm> #include <ctype.h> using namespace std; long long int fire_rampage(vector<vector<char>> &maze, long long int x, long long int y, long long int n, long long int m, vector<vector<long long 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; } long long int is_safe(vector<vector<char>> &maze, long long int x, long long int y, long long int n, long long int m, vector<vector<long long 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; } long long int Time(vector<vector<char>> &maze, long long int burn_x, long long int burn_y, long long int x, long long int y, long long int end_x, long long int end_y, long long int now, long long int notice_time, vector<vector<long long int>> &visited, vector<vector<long long int>> visited_2, vector<vector<long long int>> distance, long long int H, long long int W) { vector<deque<long long int>> queue(2); vector<deque<long long int>> queue_2(2); vector<vector<long long int>> time(H, vector<long long int>(W)); vector<long long 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; long long 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())) { auto b_x = queue_2[0].front(); auto b_y = queue_2[1].front(); if (maze[b_x][b_y] == now + 48) { for (long long int i = 0; i < 4; i++) { long long 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())) { if (now >= notice_time) { auto from_x = queue[0].front(); auto from_y = queue[1].front(); if (time[from_x][from_y] == now) { for(long long int i = 0; i < 8;i++) { long long 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() { long long int n, m; cin >> n >> m; vector<vector<char>> maze(n, vector<char>(m)); for (long long int i = 0; i < n; i++) { for (long long int j = 0; j < m; j++) { cin >> maze[i][j]; } } long long int first_burn_x, first_burn_y; long long int end_x, end_y; long long int notice_x, notice_y; long long 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<long long int>> visited(n, vector<long long int>(m)); vector<vector<long long int>> visited_2(n, vector<long long int>(m)); vector<vector<long long int>> distance(n, vector<long long int>(m)); long long 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; }