Untitled

mail@pastecode.io avatar
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;
}