Maze

[Pen72]

Hi everyone, This problem is very tough for me, would be glad if there's any advice to solve it properly.

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) .
Can you calculate the minimal time required for you to escape from the forest?

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 17
*****************
*...*.......**..*
**..*....*.*.*..*
*......*.**.**.**
*..**...**..**.**
**.....**..*.*..*
*....*..........*
*.....****.*...**
****.*.*........*
*****************
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!

#include <bits/stdc++.h>
using namespace std;
using LL = long long int;
using P = tuple<int,int>;


bool bfs(vector<string> &maze, const P START) {
    vector<int> dr {-1, 1, 0, 0}, dc {0, 0, -1, 1};
    string dir("UDLR");
    auto legal = [&](int r, int c) {
        return 0 <= r && r < (int)maze.size() && 0 <= c && c < (int)maze[0].size();
    };
    auto print_sol = [&](int r, int c) {
        string str;
        while (P(r, c) != START) {
            char d = maze[r][c];
            str.push_back(d);
            if (d == 'U') r += 1;
            else if (d == 'D') r -= 1;
            else if (d == 'L') c += 1;
            else c -= 1;
        }
        reverse(str.begin(), str.end());
        cout << str.size() << "\n";
    };
    // bfs
    queue<P> q({START});
    while (!q.empty()) {
        P f = q.front(); q.pop();
        auto [r, c] = f;
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i], nc = c + dc[i];
            if (!legal(nr, nc)) continue;
            if (maze[nr][nc] == '.') {
                maze[nr][nc] = dir[i];
                q.emplace(nr, nc);
            } else if (maze[nr][nc] == end) {
                maze[nr][nc] = dir[i];
                print_sol(nr, nc);
                return true;
            }
        }
    }
    return false;
}

int main() {
  
    int H, W; cin >> H >> W;
    vector<string> maze(H*W);
    for (auto &r : maze) cin >> r;
    int fx,fy,k,sx,sy,ex,ey;
    cin>>fx>>fy;
    cin>>k;
    cin>>sx>>sy>>ex>>ey;
    P burn(fx,fy);
    P start(sx,sy);
    P end(ex,ey);
    if (!bfs(maze,start)) {
        cout << "Help\n";
    }
}

[seeplus]

and the C++ question is?

Have you first designed the program before attempting to code?

[Pen72]

Hi, I don't know how to consider the burning areas(fx,fy) that evolves by time into the code, my mind is lost like a maze too.

[kigar64551]

I think you need to define a suitable data structure which represents the "state" at a specific time t. Part of that state is your current position (at time t) and which fields are currently burning (at time t). Consequently, I think that you'll want to have a 2D array representing the fields, so that for each field we can store whether it is burning or not. Also you want to have two integers, x and y, to store your current position.

Then you can implement the update function, which takes the previous state of time t and computes the new state for time t+1. As you already said, if a field is burning at t, then all adjacent fields will be burning at t+1. Hence, first of all look at the current state of time t and figure out all fields that are burning already; then set these fields plus all of their adjacent fields as burning in the next state of t+1. And so on...

(I'm not sure whether a filed that was burning at t is still burning at t+1 or whether it is considered to be "burned down" by then and only its adjacent fields, if not "burned down" yet, are burning in t+1)

[Pen72]

Now passed three cases, but still got three terminated due to time out and three wrong answers.

#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;
}

[kigar64551]

I suggest you add debug outputs to your program, so that you can see the state in each step, as produced by your program. Then compare this to what you would expect when using the "pen and paper" method. Try to figure out at which point your program diverges from the expected sequence of states. Then fix it ;-)

In those cases where you get the timeout: Does it finish, if you run it locally and give it enough time? Or does it get stuck in a deadlock? In the first case, your algorithm to solve the problem is too inefficient and you will have to think of a better (more efficient) approach; in the latter case, you obviously have a serious bug.

[Pen72]

Hello, I can only see the sample test cases and for those I got correct answers, the rests I can't access the input data it used and would be hard to fix it.

[lastchance]

You haven't given all of the sample test cases, the information in your question is too ambiguous and the second example in your duplicate thread (in the other section) appears to be wrong.

Are those fire-spread-by-diagonals-only correct? Seems unlikely. Please clarify in what directions the fire can move and in which directions you can move.

On timestep t what happens first - you move or the fire moves?

Explain (by drawing the maze at successive times) the examples in your duplicate post in the other section. The first example there (corresponding to your single example above) appears to be correct at 6. The second example there (which you haven't given in this thread) does not appear correct, and there is no reason that you can't escape at time 5.

@kigar64551's recommendation is a good one - you should plot the maze and burning areas at successive times

If you wish for help then please give the question and examples completely and accurately.

[Pen72]

Hi, the person can move to (x+1,y+1) (x,y+1)(x-1,y+1) (x+1,y) (x-1,y) (x+1,y-1) (x,y-1) (x-1,y-1), and fire burns at (x+1,y),(x-1,y),(x,y+1),(x,y-1)
directions:https://pasteboard.co/9ay52gxekPBS.png
sample test explanation https://pasteboard.co/ZFB6L7Lh91yR.png

[lastchance]

Yes, but your second example, given not here but in your other thread at
http://www.cplusplus.com/forum/general/283568/#msg1227744
has the wrong sample answer.

Show that second example in this thread please.

Also, the picture that you have just posted for your "sample test explanation" makes absolutely zero sense (for either example). I have no idea what the numbers there mean.

[Pen72]

Hi, for the picture of sample test 0 explanation, the number shows how the burning area can extent at time t(1,2,3,4,5...) ,S,E are start and exit, and @ implies the steps the person escapes.

[lastchance]

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <utility>
using namespace std;

vector< pair<int,int> > burnMoves   = { { -1,  0 }, {  1, 0  }, { 0, -1 }, { 0, 1 } };
vector< pair<int,int> > escapeMoves = { { -1, -1 }, { -1, 1  }, { 1, -1 }, { 1, 1 },
                                        { -1,  0 }, {  1, 0  }, { 0, -1 }, { 0, 1 } };

//=====================================================================

struct Maze
{
   int H, W;
   int k;
   int fx, fy, sx, sy, ex, ey;
   vector<string> board;
   set< pair<int,int> > burnFront;
   set< pair<int,int> > escapeFront;

   void read();
   void draw();
   void burnUpdate();
   void escapeUpdate();
   bool escaped(){ return board[ex][ey] == 'o'; }
};

//=====================================================================

void Maze::read()
{
   string dummy;
   cin >> H >> W;   getline( cin, dummy );
   board.resize( H );
   for ( string &line : board ) getline( cin, line );
   cin >> fx >> fy >> k >> sx >> sy >> ex >> ey;
   board[sx][sy] = 'o';
   board[ex][ey] = 'e';
   board[fx][fy] = 'b';
   burnFront   = { { fx, fy } };
   escapeFront = { { sx, sy } };
   for ( int i = 2; i <= k; i++ )
   {
//    cout << "Situation at " << i - 1 << '\n';   draw();
      burnUpdate();
   }
}

//=====================================================================

void Maze::draw()
{
   for ( string &line : board ) cout << line << '\n';
   cout << "\n\n";
}

//=====================================================================

void Maze::burnUpdate()
{
   const string nogo = "be*";
   set< pair<int,int> > newFront;
   for ( auto pr : burnFront )
   {
      for ( auto delta : burnMoves )
      {
         int x = pr.first  + delta.first ;
         int y = pr.second + delta.second;
         if ( x >= 0 && x < W && y >= 0 && y < H && nogo.find( board[x][y] ) == string::npos )
         {
            board[x][y] = 'b';
            newFront.insert( { x, y } );
         }
      }
   }
   burnFront = newFront;
}

//=====================================================================

void Maze::escapeUpdate()
{
   const string nogo = "bo*";
   set< pair<int,int> > newFront;
   for ( auto pr : escapeFront )
   {
      if ( board[pr.first][pr.second] != 'b' )
      {
         for ( auto delta : escapeMoves )
         {
            int x = pr.first  + delta.first ;
            int y = pr.second + delta.second;
            if ( x >= 0 && x < W && y >= 0 && y < H && nogo.find( board[x][y] ) == string::npos )
            {
               board[x][y] = 'o';
               newFront.insert( { x, y } );
            }
         }
      }
   }
   escapeFront = newFront;
}

//=====================================================================

int main()
{
   Maze maze;
   maze.read();
// cout << "Situation at " << maze.k << '\n';   maze.draw();

   for ( int t = maze.k; !maze.escapeFront.empty(); t++ )
   {
      if ( maze.escaped() )
      {
         cout << t - maze.k << '\n';
         return( 0 );
      }
      maze.escapeUpdate();
      maze.burnUpdate();
//    cout << "Situation at " << t + 1 << '\n';   maze.draw();
   }
   cout << "Help!\n";
}

//===================================================================== 

[Pen72]

Hi, There are still four out of nine wrong ans, the rests are correct. What does !maze.escapeFront.empty() means in line114, why would it be empty. And why can we output the steps once we got maze.escaped() ==1 in line116, doesn't bool escaped(){ return board[ex][ey] == 'o'; } just returns an available escape position rather than saying we've reached the exit.

[lastchance]

maze.escapeFront holds the latest set of positions that one can escape to. When this is empty there is nowhere else to go, so the time-iteration must stop.

maze.escaped returns true if the possible escape positions have reached the exit: at which point you can output the time as required by the question.

You can see what is happening by uncommenting the three lines that draw the maze. Maybe you will be able to detect differences with the picture that you posted to illustrate the first example.

The program iteratively expands the set of points that can be reached, marking them 'b' for burnt and 'o' for escaping person. The exit point is marked 'e'. The "fronts" are the current boundaries of these points. The original maze markings are '*' for obstacle and '.' for unused.

It would be difficult to go further without seeing the data that caused a problem.

[lastchance]

OK, try this one. (I've flipped the limits of x and y around.)

For debugging purposes you can set VERBOSE to true at the start and see the changing maze.

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <utility>
using namespace std;

bool VERBOSE = false;   // change to true to see the changing situation

vector< pair<int,int> > burnMoves   = { { -1,  0 }, {  1, 0  }, { 0, -1 }, { 0, 1 } };
vector< pair<int,int> > escapeMoves = { { -1, -1 }, { -1, 1  }, { 1, -1 }, { 1, 1 },
                                        { -1,  0 }, {  1, 0  }, { 0, -1 }, { 0, 1 } };

//=====================================================================

struct Maze
{
   int H, W;
   int k;
   int fx, fy, sx, sy, ex, ey;
   vector<string> board;
   set< pair<int,int> > burnFront;
   set< pair<int,int> > escapeFront;

   void read();
   void draw();
   void burnUpdate();
   void escapeUpdate();
   bool escaped(){ return board[ex][ey] == 'o'; }
};

//=====================================================================

void Maze::read()
{
   string dummy;
   cin >> H >> W;   getline( cin, dummy );
   board.resize( H );
   for ( string &line : board ) getline( cin, line );
   cin >> fx >> fy >> k >> sx >> sy >> ex >> ey;
   board[sx][sy] = 'o';
   board[ex][ey] = 'e';
   board[fx][fy] = 'b';
   burnFront   = { { fx, fy } };
   escapeFront = { { sx, sy } };
   for ( int i = 1; i < k; i++ )
   {
      if ( VERBOSE ) { cout << "Time " << i << '\n';   draw(); }
      burnUpdate();
   }
}

//=====================================================================

void Maze::draw()
{
   for ( string &line : board ) cout << line << '\n';
   cout << "\n\n";
}

//=====================================================================

void Maze::burnUpdate()
{
   const string nogo = "be*";
   set< pair<int,int> > newFront;
   for ( auto pr : burnFront )
   {
      for ( auto delta : burnMoves )
      {
         int x = pr.first  + delta.first ;
         int y = pr.second + delta.second;
         if ( x >= 0 && x < H && y >= 0 && y < W && nogo.find( board[x][y] ) == string::npos )
         {
            board[x][y] = 'b';
            newFront.insert( { x, y } );
         }
      }
   }
   burnFront = newFront;
}

//=====================================================================

void Maze::escapeUpdate()
{
   const string nogo = "bo*";
   set< pair<int,int> > newFront;
   for ( auto pr : escapeFront )
   {
      if ( board[pr.first][pr.second] != 'b' )
      {
         for ( auto delta : escapeMoves )
         {
            int x = pr.first  + delta.first ;
            int y = pr.second + delta.second;
            if ( x >= 0 && x < H && y >= 0 && y < W && nogo.find( board[x][y] ) == string::npos )
            {
               board[x][y] = 'o';
               newFront.insert( { x, y } );
            }
         }
      }
   }
   escapeFront = newFront;
}

//=====================================================================

int main()
{
   Maze maze;
   maze.read();
   if ( VERBOSE ) { cout << "Time " << maze.k << '\n';   maze.draw();   cout << "Start moving ...\n\n"; }

   for ( int t = maze.k + 1; !maze.escapeFront.empty(); t++ )
   {
      maze.escapeUpdate();
      if ( maze.escaped() )
      {
         if ( VERBOSE ) { cout << "EXIT during time " << t << '\n';   maze.draw(); }
         cout << t - maze.k << '\n';
         return 0;
      }
      maze.burnUpdate();
      if ( VERBOSE ) { cout << "Time " << t << '\n';   maze.draw(); }
   }
   cout << "Help!\n";
}

//===================================================================== 

For your first example, with VERBOSE changed to true:

Time 1
*****************
*b..*.......**..*
**..*....*.*.*..*
*..e...*.**.**.**
*o.**...**..**.**
**.....**..*.*..*
*....*..........*
*.....****.*...**
****.*.*........*
*****************


Time 2
*****************
*bb.*.......**..*
**..*....*.*.*..*
*..e...*.**.**.**
*o.**...**..**.**
**.....**..*.*..*
*....*..........*
*.....****.*...**
****.*.*........*
*****************


Time 3
*****************
*bbb*.......**..*
**b.*....*.*.*..*
*..e...*.**.**.**
*o.**...**..**.**
**.....**..*.*..*
*....*..........*
*.....****.*...**
****.*.*........*
*****************


Time 4
*****************
*bbb*.......**..*
**bb*....*.*.*..*
*.be...*.**.**.**
*o.**...**..**.**
**.....**..*.*..*
*....*..........*
*.....****.*...**
****.*.*........*
*****************


Start moving ...

Time 5
*****************
*bbb*.......**..*
**bb*....*.*.*..*
*bbe...*.**.**.**
*ob**...**..**.**
**o....**..*.*..*
*....*..........*
*.....****.*...**
****.*.*........*
*****************


Time 6
*****************
*bbb*.......**..*
**bb*....*.*.*..*
*bbe...*.**.**.**
*bb**...**..**.**
**bo...**..*.*..*
*ooo.*..........*
*.....****.*...**
****.*.*........*
*****************


Time 7
*****************
*bbb*.......**..*
**bb*....*.*.*..*
*bbe...*.**.**.**
*bb**...**..**.**
**bbo..**..*.*..*
*oboo*..........*
*oooo.****.*...**
****.*.*........*
*****************


Time 8
*****************
*bbb*.......**..*
**bb*....*.*.*..*
*bbe...*.**.**.**
*bb**o..**..**.**
**bbbo.**..*.*..*
*bbbo*..........*
*obooo****.*...**
****o*.*........*
*****************


Time 9
*****************
*bbb*.......**..*
**bb*....*.*.*..*
*bbeooo*.**.**.**
*bb**oo.**..**.**
**bbbbo**..*.*..*
*bbbb*o.........*
*bbboo****.*...**
****o*o*........*
*****************


EXIT during time 10
*****************
*bbb*.......**..*
**bb*ooo.*.*.*..*
*bboooo*.**.**.**
*bb**ooo**..**.**
**bbbbo**..*.*..*
*bbbb*oo........*
*bbboo****.*...**
****o*o*........*
*****************


6

[Pen72]

HI, yes it's better, what's the reason of putting the limits of x and y around.

[lastchance]

HI, yes it's better

Did it pass all cases, or is it just "better"?

what's the reason of putting the limits of x and y around.

Because I got them wrong in the earlier code! But then I know which directions x and y usually go in ...


The only meaningful things I did in the last code (other than make it easier to switch on and off the debugging) were to change the order of updates at time t in main() to:
- update escape front
- check for exit
- update burn front
This order isn't obvious from the question, though one of the pictures that was posted later helped to clarify it.


When you post a problem you need to:
- post the original description (not your paraphrasing of it);
- post all available sample test cases (some of the questions leave a lot of ambiguity);
- post all available pictures - one of those was crucial for deciding the order of updates.


Clearly, my method looks nothing like yours. Perhaps in this case I have the advantage of not having done a Computer Science degree, so allowing me to follow my imagination and intuition rather than a prescribed algorithm.

[ElusiveTau]

@lastchance @Pen72

This smells like an Amazon technical interview question. There are variants of this problem description online (i.e., OP is likely recalling how it was described during the interview).

Still, it would be nice to have this disclaimer so people understand that the problem statement might not be well-defined/opened to interpretation (How long does a position burn and does it become navigable again after some time? Is it possible for fires to spread and create an unsolvable maze after some time (or are the starting fire position determined such that the maze is always solvable?))

I feel like this question is better served in a blog-post (and linked here) where you can explain your design choices and post pictures. Test code/test cases to be posted on a GitHub repo.

Interesting problem in of itself though ... a maze with moving walls :)

[lastchance]

@ElusiveTau, I presume it was one of the more advanced testing sites like leetcode; not homework anyway. Interesting (and a little frustrating) to try, and I'm expanding my graph theory all the time!

I don't know how standard the OP's approach is, but where he/she sees "Breadth-First Search" I see "Diffusion Problem", so I probably wouldn't be speaking the same language as those conducting an Amazon technical interview.

Interesting problem in of itself though ... a maze with moving walls :)

Agreed.

[Pen72]

Hello, thanks for all the replies. Yeah seeing one problem from different angles are interesting. @lastchance your code pass all test cases except one.
And updated below is the newly provided solution that can pass all cases.

#include <bits/stdc++.h>
using namespace std;

char mp[60][60];
int ft[60][60];
int rt[60][60];
int main() {
    int W, H;

    cin >> H >> W;
    for (int i=0;i<H;++i)
        cin >> mp[i];
    int fx, fy;
    int t;
    int sx, sy, ex, ey;

    cin >> fx >> fy
        >> t
        >> sx >> sy >> ex >> ey;

    int dx[] = {1,-1,0,0};
    int dy[] = {0,0,1,-1};

    queue<tuple<int,int>> qu;

    memset(ft, 0x3f, sizeof(ft));
    const int INF = ft[0][0];

    qu.emplace(fx, fy);
    ft[fx][fy] = 1;

    while (!qu.empty()) {
        auto [x, y] = qu.front();
        qu.pop();

        for (int i=0;i<4;++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || H <= nx) continue;
            if (ny < 0 || W <= ny) continue;
            if (mp[nx][ny] != '.' || ft[nx][ny]!=INF) continue;
            if (nx == ex && ny == ey) continue;

            ft[nx][ny] = 1 + ft[x][y];
            qu.emplace(nx, ny);
        }
    }

    memset(rt, 0x3f, sizeof(rt));

    qu.emplace(sx, sy);
    rt[sx][sy] = t;

    int d8x[] = {1,1,1,0,0,-1,-1,-1};
    int d8y[] = {1,0,-1,1,-1,1,0,-1};

    while (!qu.empty()) {
        auto [x, y] = qu.front();
        qu.pop();

        for (int i=0;i<8;++i) {
            int nx = x + d8x[i];
            int ny = y + d8y[i];

            if (nx < 0 || H <= nx) continue;
            if (ny < 0 || W <= ny) continue;
            if (mp[nx][ny] != '.' || rt[nx][ny]!=INF) continue;
            if (1 + rt[x][y] >= ft[nx][ny]) continue;

            rt[nx][ny] = 1 + rt[x][y];
            qu.emplace(nx, ny);
        }
    }

    if (rt[ex][ey] == INF) cout << "Help!\n";
    else cout << rt[ex][ey] - t << '\n';
}