# Untitled

unknown
plain_text
2 years ago
5.4 kB
6
Indexable
Never
```//想法是有兩個 bfs 一個是火焰的 一個是人的逃跑路線

#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;
}
```