c - I was trying to solve this maze with the following code. But the answers aren't accurate for all inputs like n=4 -

maze problem

you provided matrix of size n*n source position @ (0,0) , destination @ (n-1,n-1) in 2d array. of positions in array marked 0 blocked cells, rest being marked 1.

a path connected sequence of elements (0,0) (n-1,n-1) consists of 1. sequence of 1s in 2d array connected if every 1 in sequence adjacent (the above or left neighbour) next 1 in sequence.

for example, in following matrix,

1 1 0 0 1 1 1 0 1  

the 1s marked in blue connected path (0,0) (2,2)

note cells @ (0,0) , (n-1,n-1) 1. can either make movement towards right or down, i.e., position (x,y), can go either position (x,y+1) or (x+1,y).

input

first line consists of size of input array n (<=50), following state of nxn maze consist of 0s , 1s.

output

you have print "possible" if there exists path between source , destination otherwise print "not possible".

problematic cases

for following input,

4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

the console displays not possible whereas correct output should possible.

c code

#include<stdio.h>  #define true 1 #define false 0 // maze size int n;  int solvemazeutil(int maze[n][n], int x, int y, int sol[n][n]);  /* utility function print solution matrix sol[n][n] */ void printsolution(int sol[n][n]) {     (int = 0; < n; i++)     {         (int j = 0; j < n; j++)             printf(" %d ", sol[i][j]);         printf("\n");     } }  /* utility function check if x,y valid index n*n maze */ int issafe(int maze[n][n], int x, int y) {     // if (x,y outside maze) return false     if(x >= 0 && x < n && y >= 0 && y < n && maze[x][y] == 1)         return true;      return false; }  /* function solves maze problem using backtracking.  uses solvemazeutil() solve problem. returns false if no path possible, otherwise return true , prints path in form of 1s. please note there may more 1 solutions, function prints 1 of feasible solutions.*/ int solvemaze(int maze[n][n]) {     int sol[n][n] = { {0, 0, 0, 0},         {0, 0, 0, 0},         {0, 0, 0, 0},         {0, 0, 0, 0}     };      if(solvemazeutil(maze, 0, 0, sol) == false)     {         printf("not possible");         return false;     } printf("possible");    // printsolution(sol);     return true; }  /* recursive utility function solve maze problem */ int solvemazeutil(int maze[n][n], int x, int y, int sol[n][n]) {     // if (x,y goal) return true     if(x == n-1 && y == n-1)     {         sol[x][y] = 1;         return true;     }      // check if maze[x][y] valid     if(issafe(maze, x, y) == true)     {         // mark x,y part of solution path         sol[x][y] = 1;          /* move forward in x direction */         if (solvemazeutil(maze, x+1, y, sol) == true)             return true;          /* if moving in x direction doesn't give solution            move down in y direction  */         if (solvemazeutil(maze, x, y+1, sol) == true)             return true;          /* if none of above movements work backtrack:              unmark x,y part of solution path */         sol[x][y] = 0;         return false;     }         return false; }  // driver program test above function int main() {     int n;     scanf("%d",&n);     n=n;     int maze[52][52]  ;     for(int i=0;i<n;i++)         for(int j=0;j<n;j++)         {             scanf("%d",&maze[i][j]);         }     solvemaze(maze);     return 0; } 

this interesting problem dynamic-programming comes handy. in fact example use whenever asks me dynamic programming.

now here questions worth considering:

if cell 0, still possible reach cell?

if cell 1, how know reach cell? different ways use cell?

the first question obvious. if cell 0 cannot reached.

the second question less so, still quite straightforward: cell can reached in 2 ways: the cell above or the cell left.

now have made these observation, know given last cell (n-1, n-1), know can reached if:

1. the cell 1 &&
2. the cell above or cell left can reached.

recursively, find out if there such path recursively call 2 cells if current cell 1.

---

now, that's not efficient. in worst case cells 1, complexity exponential. how can better?

what first column , first row of maze? when can reached?

cells in first row/column can reached in one way (imagine row -1 , col -1 filled 0) , know cell (0,0) 1, can iteratively find out reachability of cells in first row/col. first row/col, same second row/col!

in other words, states of 1 row depends on row above it; states of 1 column depends on column left. have row/col -1 definition, rest can computed iteratively, row row, in o(n^2).

i intentionally did not provide code thought process more valuable here. hope helps!