BFS迷宮问题请求相救

Question

请求相救 此题代码过四笔测资但有三笔超时和三笔错误答案。

/*There is a forest fire and you are in the forest.

If an area (x,y) burns at time t, the adjacent area (x+1,y),(x-1,y),(x,y+1),(x,y-1) will burn at time t+1 .

Unfortunately, when you are notified, the forest fire has been lasting for minutes after the first burning area was reported.

If you are in (x,y) at time t , you can only move to (x+/-1,y+/-1) at time t+1.

The only exit of the forest is in (ex,ey), and there are some obstacles in the forest.

Note that the exit and obstacles(*) are NOT burnable.

Can you calculate the minimal time required for you to escape from the forest?

At time 1, the first burning area is in (fx,fy) .
At time k, you are in (sx,sy) .
Input Format

The first line is H,W which is height and width of the map for the forest.

The following H line is the map, and there are W characters in each line.

Following the lines for map, there are remaining 3 lines:

The first line is (fx,fy), which is the coordinates of the first burning area.
The second line is k, which is the elapsed time after the first burning area was reported.
The third line is (sx,sy) and (ex,ey) , which are the coordinates of you when you are notified and the coordinates of the exit.
Constraints

The range of coordinates is (0,0) to (H-1,W-1)
The top left coordinates of the map is(0,0) .
The down right coordinates of the map is (H-1,W-1).
All coordinates in input are distinct.
Output Format

If you can safely escape from the forest, print the minimal time required; otherwise, print Help! instead.

Sample Input 0

10 18
*****************
*...*.......**..*
**..*....*.*.*..*
*......*.**.**.**
*..**...**..**.**
**.....**..*.*..*
*....*..........*
*.....****.*...**
****.*.*........*
*****************
1 1
4
4 1 3 3
Sample Output 0

6
*/

#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())) 
        {
            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())) 
        {
            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()
{
    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 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;
}