C++

Forum

 
Puzzle problem

Pen72 (74)
Got confused in what sort of algorithms should I implement here?

Given a R*C rectangular grid maze where each cell is either empty or a wall. You can go from a cell to another in a step if both cells are empty and have a common side. That is, from an empty cell, you can go up, down, left, right to another cell in a step if it is empty. Given the cell you start from, please output the minimum steps to go to the destination cell, or report that it is impossible to reach the destination cell.

Input Format
The first line has two integers R,C : the number of rows and the number of columns of the maze.

Then there are R lines with C characters in each line describing the maze.# denotes the cell is a wall. . denotes the cell is empty. A is the cell you start from. B is the destination cell.

Output Format

Output the minimum steps in one line. If it is impossible to reach the destination cell, please output "IMPOSSIBLE" in one line.

Sample Input 0

5 8
########
#.A#...#
#.##.#B#
#......#
########
Sample Output 0

9

1
2
3
4
5
6
7
8
9
10
11
 
  int main() {
    int r,c;
    string str;
    cin>>r>>c;
    while(r--)
    vector<string>A[r];
    for(int i=0;i<r;i++)
        cin>>str;
    
    return 0;
}
dhayden (5798)
I haven't had enough coffee yet, but I think this is Djkstra's shortest path.
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Starting at A, find all the cells that can be reached with one move and add them to a list.
Now go through the list of cells whose distance is 1 and build up a list of all the cells whose distance is 2. Be careful not to backtrack onto a cell that's already distance 1.

Now starting at cells of distance 2, find the cells that are distance 3.

Keep going like that until you reach B.
Pen72 (74)
Need help on this attempt, it passed few test cases but shows segmentation fault and terminated due to time out in few cases too.
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
 
#include <cmath>
#include <cstdio>
#include <vector>
#include <deque>
#include <iostream>
#include <algorithm>
using namespace std;

uint64_t is_safe(vector<vector<char>> maze,uint64_t x,uint64_t y,uint64_t n,uint64_t m,vector<vector<uint64_t>> visited)
{
    if(maze[x][y] != '#' && x<n && x>=0 && y<m && y>=0 && visited[x][y] == 0)
        return 1;
    else return 0;
}

int main() {
  
    uint64_t n,m;
    cin  >> n >> m;
    vector<vector<char>> maze (n,vector<char>(m));
    uint64_t initi_x ;
    uint64_t initi_y ;
    uint64_t end_x ;
    uint64_t end_y ;
    for (uint64_t i = 0; i < n; i++)
    {
        for (uint64_t j = 0; j < m; j++)
        {
            char content;
            cin >> content;
            if (content == 'A')
                initi_x = i,initi_y = j;
            if (content == 'B')
                end_x = i,end_y = j;
            maze[i][j] = content;
        }
    }
    vector<deque<uint64_t>> queue(2);
    vector<vector<uint64_t>> visited (n+1,vector<uint64_t>(m+1));
    vector<vector<uint64_t>> distance(n+1,vector<uint64_t>(m+1));
    uint64_t max = 0;
    bool flag = false;
    queue[0].push_front(initi_x),queue[1].push_front(initi_y);
    visited[initi_x][initi_y] = 1;
    while(!(queue[0].empty() && queue[1].empty()))
    {
        auto from_x = queue[0].front(); auto from_y = queue[1].front();  
        if(is_safe(maze,from_x+1,from_y,n,m,visited)) 
        {
            visited[from_x+1][from_y] = 1;
            distance[from_x+1][from_y] = distance[from_x][from_y]+1;
            if(from_x+1 == end_x && from_y == end_y) {flag = true;max = distance[from_x+1][from_y]; break;}
            queue[0].push_back(from_x+1),queue[1].push_back(from_y);
        }
        if(is_safe(maze,from_x-1,from_y,n,m,visited)) 
        {
            visited[from_x-1][from_y] = 1;
            distance[from_x-1][from_y] = distance[from_x][from_y]+1;
            if(from_x-1 == end_x && from_y == end_y) {flag = true;max = distance[from_x-1][from_y]; break;}
            queue[0].push_back(from_x-1),queue[1].push_back(from_y);
        }
        if(is_safe(maze,from_x,from_y+1,n,m,visited)) 
        {
            visited[from_x][from_y+1] = 1;
            distance[from_x][from_y+1] = distance[from_x][from_y]+1;
            if(from_x == end_x && from_y+1 == end_y) {flag = true;max = distance[from_x][from_y+1]; break;}
            queue[0].push_back(from_x),queue[1].push_back(from_y+1);
        }
        if(is_safe(maze,from_x,from_y-1,n,m,visited))
        {
            visited[from_x][from_y-1] = 1;
            distance[from_x][from_y-1] = distance[from_x][from_y]+1;
            if(from_x == end_x && from_y-1 == end_y) {flag = true;max = distance[from_x][from_y-1]; break;}
            queue[0].push_back(from_x),queue[1].push_back(from_y-1);
        }
        queue[0].pop_front(); queue[1].pop_front();
    }
    if(flag == false) {cout << "IMPOSSIBLE" ;}
    else {cout << max ;}
    return 0;
}
Last edited on
lastchance (6980)
@Pen72,

My compiler says
test1.cpp: In function 'uint64_t is_safe(std::vector<std::vector<char> >, uint64_t, uint64_t, uint64_t, uint64_t, std::vector<std::vector<long long unsigned int> >)':
test1.cpp:11:37: warning: comparison of unsigned expression >= 0 is always true [-Wtype-limits]
     if(maze[x][y] != '#' && x<n && x>=0 && y<m && y>=0 && visited[x][y] == 0)
                                    ~^~~
test1.cpp:11:52: warning: comparison of unsigned expression >= 0 is always true [-Wtype-limits]
     if(maze[x][y] != '#' && x<n && x>=0 && y<m && y>=0 && visited[x][y] == 0)
                                                   ~^~~

Last edited on
seeplus (6591)
@Pen72 - now's the time to learn to use the debugger if you don't already know. Use the debugger to trace through the code and watch the variables and see where the code execution varies from that expected from your program design. Once found, then you have found an error. Then fix that issue and repeat until the program works as expected.

Knowing how to use the debugger is a skill that all programmers need to acquire - and IMO sooner rather than later.
Last edited on
lastchance (6980)

Method is essentially that of @dhayden (except that I don't bother to mark cells by steps, just keep a set containing the current front).

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
 
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <cstdlib>
using namespace std;

using PR = pair<int,int>;

long long runCase()
{
   PR A, B;
   int R, C;

   // Read the grid (expand boundaries by 1 to fudge as walls)
   cin >> R >> C;
   vector< vector<bool> > G( R + 2, vector<bool>( C + 2, false ) );
   for ( int i = 1; i <= R; i++ )
   {
      string row;
      cin >> row;
      for ( int j = 1; j <= C; j++ )
      {
         if ( row[j-1] != '#' ) G[i][j] = true;
         if ( row[j-1] == 'A' ) A = { i, j };
         if ( row[j-1] == 'B' ) B = { i, j };
      }
   }

   // Iteratively spread out the front
   set<PR> last, current = { A };
   for ( long long steps = 1; !current.empty(); steps++ )
   {
      last = current;
      current.clear();
      // Insert pristine cells into set "current"; i.e. those updated at this step
      for ( PR pr : last )
      {
         int i = pr.first, j = pr.second;
         // Test for end
         if ( abs( i - B.first ) + abs( j - B.second ) == 1 ) return steps;
         // Add any adjacent available cells into "current"
         if ( G[i+1][j] ) current.insert( { i + 1, j } );
         if ( G[i-1][j] ) current.insert( { i - 1, j } );
         if ( G[i][j+1] ) current.insert( { i, j + 1 } );
         if ( G[i][j-1] ) current.insert( { i, j - 1 } );
      }
      // Mark all cells in "current" as taken
      for ( PR pr : current ) G[pr.first][pr.second] = false;
   }
   return -1;
}



int main()
{
   long long steps = runCase();
   if ( steps > 0 ) cout << steps        << '\n';
   else             cout << "IMPOSSIBLE" << '\n';
}

Last edited on
Topic archived. No new replies allowed.