Untitled

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