C++

Forum

 
BFS maze

Pen72 (74)
Hello, I've been trapped by this problem for days. Now passed three cases, but still got three terminated due to time out and three wrong answers. I really want to figure out how to solve it. Many thanks.

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

Sample Input 1

10 17
*****************
*...*.......**..*
**..*....*.*.*..*
*......*.**.**.**
*..**...**..**.**
**.....**..*.*..*
*....*..........*
*.....****.*...**
****.*.*........*
*****************
1 1
3
4 1 2 3
Sample Output 1

Help!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
 
#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;
}
Last edited on
TheIdeasMan (6817)
Last edited on
zapshe (1907)
Same subject, but they've gotten further in their code and are now stuck somewhere else.

That being said, you should show the cases where your code is failing and why.
seeplus (6591)
@zapshe - that's the problem and why I haven't tried. The actual input is unknown so it's not possible to debug with actual data - only test cases for which it works.
Topic archived. No new replies allowed.