### BFS maze

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!

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143`` ``````#include #include #include #include #include #include #include using namespace std; int fire_rampage(vector> &maze, int x, int y, int n, int m, vector> &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> &maze, int x, int y, int n, int m, vector> &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> &maze, int burn_x, int burn_y, int x, int y, int end_x, int end_y, int now, int notice_time, vector> &visited, vector> visited_2, vector> distance, int H, int W) { vector> queue(2); vector> queue_2(2); vector> time(H, vector(W)); vector 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> maze(n, vector(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> visited(n, vector(m)); vector> visited_2(n, vector(m)); vector> distance(n, vector(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
Last edited on
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.
@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.