0

I need to develop and implement the algorithm that will produce the path existing in between the first pixel and the last pixel.

INPUT:line 1 the size of the grid is M×N. line 2:space separated 5 numbers. The first is an integer, say i, representing a pixel number followed by a sequence of four bits (0/1) showing the directions one can move from pixel i.

Sample Input:

5 8
1 0 1 1 0
2 0 1 1 1
3 0 1 0 1
4 0 0 1 1
5 0 1 1 0
6 0 1 1 1
7 0 1 0 1
8 0 0 1 1
9 1 1 1 0
10 1 0 0 1
11 0 1 0 0
12 1 0 1 1
13 1 0 1 0
14 1 1 0 0
15 0 0 1 1
16 1 0 1 0
17 1 0 1 0
18 0 1 1 0
19 0 1 0 1
20 1 0 1 1
21 1 0 1 0
22 0 1 1 0
23 1 0 0 1
24 1 0 0 0
25 1 0 1 0
26 1 1 0 0
27 0 0 1 1
28 1 0 1 0
29 1 0 1 0
30 1 0 1 0
31 0 1 1 0
32 0 0 1 1
33 1 1 0 0
34 0 0 0 1
35 1 0 0 0
36 1 1 0 0
37 1 0 0 1
38 1 1 0 0
39 0 1 0 1
40 1 0 0 1

Output:display the numbers traversed in the path.(RIGHT NOW I AM JUST PRINTING THE PATHS REPRESENTING 1 INFORM OF MATRIX(sol))

I am facing segmentation error at this line if (isSafe(t,x,y)==true && solveMazeUtil( t,r,b,l, x - 1, y, sol) == true) and i think there is problem with logic. THANKS IN ADVANCE!! sample pixel image

#include <bits/stdc++.h>

#define max 1000
using namespace std;
// Maze size 
int m, n;

bool solveMazeUtil(int t[], int r[], int b[], int l[], int x, int y, int ** sol);

void printSolution(int ** sol) {
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++)
      cout << sol[i][j];
    cout << "\n";
  }
}

/* A utility function to check if x, 
y is valid directions */
bool isSafe(int check[], int x, int y) {
  // if (x, y outside maze) return false 
  if (x < 0 || x >= m) return false;
  if (y < 0 || y >= n) return false;
  int ind = x * n + y;
  return (check[ind] == 1);

}

/* This function solves the Maze problem 
using Backtracking. It mainly uses 
solveMazeUtil() to solve the problem. 
It returns false if no path is possible, 
otherwise return true and prints the path 
in the form of 1s. */
bool solveMaze(int t[], int r[], int b[], int l[]) {
  int ** sol;
  sol = new int * [m];
  for (int i = 0; i < n; i++)
    sol[i] = new int[n];
  std::fill(sol[0], sol[0] + m * n, 0);

  if (solveMazeUtil(t, r, b, l, 0, 0, sol) == true) {
    printSolution(sol);
    return true;
  }

  return false;
}

/* A recursive utility function 
 */
bool solveMazeUtil(int t[], int r[], int b[], int l[], int x, int y, int ** sol) {
  sol[x][y] = 1;
  // if (x, y is goal) return true 
  if (x == m - 1 && y == n - 1) {
    return true;
  }
  if (isSafe(t, x, y) == true && solveMazeUtil(t, r, b, l, x - 1, y, sol) == true)
    return true;
  if (isSafe(r, x, y) == true && solveMazeUtil(t, r, b, l, x + 1, y, sol) == true)
    return true;
  if (isSafe(b, x, y) == true && solveMazeUtil(t, r, b, l, x, y + 1, sol) == true)
    return true;
  if (isSafe(l, x, y) == true && solveMazeUtil(t, r, b, l, x, y - 1, sol) == true)
    return true;
  /* If none of the above movements 
  work then BACKTRACK: unmark 
  x, y as part of solution path */
  sol[x][y] = 0;
  return false;

  return false;
}

// driver program to test above function 
int main() {
  int t[max], r[max], l[max], b[max], v[max];
  cin >> m >> n;
  for (int i = 0; i < m * n; i++) {
    cin >> v[i] >> t[i] >> r[i] >> b[i] >> l[i];
  }
  solveMaze(t, r, b, l);
  return 0;
}
JHBonarius
  • 10,824
  • 3
  • 22
  • 41
xyz_athema
  • 1
  • Don't use `#include `. Also, use `std::vector`. And learn to use a debugger. – JHBonarius Nov 28 '20 at 16:45
  • @JHBonarius I used it but couldnt figure out the reason . Also i am a novice so it would be great if you can help with the problem. – xyz_athema Nov 28 '20 at 16:47
  • 1
    Look at this line `std::fill(sol[0], sol[0] + m * n, 0);`... you're assuming all the arrays you create with `new` are stored sequentially on the heap... that's false. – JHBonarius Nov 28 '20 at 16:49
  • Basic debugger use you can pick up pretty fast. Step through the program line by line until you spot it do something (take the wrong path, store the wrong value in a variable, crash, etc...) you don't expect. That's usually a bug. Once you're used to that look up breakpoints. They let you quickly get to places in the code you want to inspect more closely. – user4581301 Nov 28 '20 at 16:58
  • @JHBonarius This is actually one of the methods i picked up from internet to initialize all elements of the 2d array to 0 – xyz_athema Nov 28 '20 at 17:01
  • 1
    first: not everything on the web is correct/true/good practice. Secondly: this will only work with stack-allocated (fixed size) arrays. Not with heap-allocated arrays. – JHBonarius Nov 28 '20 at 17:10
  • If you are allowed to use `std::vector` for this job, here's [a link to a really simple and safe matrix class](https://stackoverflow.com/a/2076668/4581301) that automatically initializes the contents to 0. – user4581301 Nov 28 '20 at 18:42

1 Answers1

2

It is very important to write readible code. It will help you make less mistakes and will also make it easier to maintain the code in the future. An important aspect is variable naming. I had to think about it myself. but t, r, b, l probably denote "top" "right" "bottom" and "left.

Now let me rewrite a part of your code (leaving out the not properly encapsulated stuff):

    if ((isSafe(top)    && solveMazeUtil(x - 1, y)) ||
        (isSafe(right)  && solveMazeUtil(x + 1, y)) ||
        (isSafe(bottom) && solveMazeUtil(x, y + 1)) ||
        (isSafe(left)   && solveMazeUtil(x, y - 1))) return true;

Do you see the problem?

edit: I also see that you've got your indexing wrong. Numbering in the cells goes like:

 1  2  3  4  5  6  7  8
 9 10 11 12 13 14 15 16
17 18 19 20 ...

thus the index in the arrays need to be x + y*N.

JHBonarius
  • 10,824
  • 3
  • 22
  • 41