Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




Edit

Rat in a maze problem using backtracking | FACE Prep

Published on 11 Mar 2020

Program to solve Rat in a maze problem using backtracking is discussed here. Given a maze where 1 represent free space and 0 represented it is blocked. Print the path from 0,0 to n-1, n-1 if exists or print -1;


Consider the maze given below.

rat in a maze problem

Gray blocks represent dead ends (value = 0) and path can be traced only using the white path (value = 1).


The binary matrix representation of the above maze (a) is given as


{1, 0, 0, 0}
{1, 0, 0, 0}
{1, 1, 1, 1}
{0, 0, 0, 1}


The highlighted lines in (b) show the path to reach the destination from the source.


Algorithm for rat in a maze problem


1. If the destination point is reached,

  • Print the solution_matrix.


2. Else

  • Mark the current cell in the solution_matrix as 1.
  • Move forward in the horizontal direction and recursively check if this move leads to the solution.
  • If the move chosen in the above step doesn't lead to a solution then move down and check if this move leads to the solution.
  • If none of the above solutions works then unmark this cell as 0 (backtrack) and return false.


Program for rat in a maze problem


C++

Output
Input - 3
1 1 0
0 1 1
1 1 1
Output -
1 1 0
0 1 0
0 1 1


Test Case 1

I/P

3

1 1 0

0 1 1

1 1 1


O/P

1 1 0

0 1 0

0 1 1


Test Case 2

I/P

5

1 1 0 0 1

0 1 1 1 0

1 1 1 0 1

1 1 1 1 1

1 1 1 1 1


O/P

1 1 0 0 0

0 1 0 0 0

0 1 0 0 0

0 1 0 0 0

0 1 1 1 1


Test Case 3

I/P

5

1 0 0 0 1

0 1 1 1 0

1 1 1 0 1

1 1 1 1 1

1 1 1 1 1


O/P

-1


Test Case 4

I/P

4

0 0 0 0

1 0 0 1

1 1 1 1

1 0 0 1


O/P

-1


Test Case 5

I/P

4

1 0 0 0

1 0 0 1

1 1 1 1

1 0 0 1


O/P

1 0 0 0

1 0 0 0

1 1 1 1

0 0 0 1


Recommended Programs





If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in
Explore 'c plus plus'
Articles Practice Exercises