-
Notifications
You must be signed in to change notification settings - Fork 1
/
backTracking.cpp
65 lines (61 loc) · 1.09 KB
/
backTracking.cpp
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
///rat in a maze
#include<bits/stdc++.h>
using namespace std;
bool isSafe(int** arr,int x,int y,int n){
if(x<n && y<n && arr[x][y]==1){
return true;
}
return false;
}
bool ratinMaze(int** arr, int x,int y,int n,int** solArr){
if(x==n-1 && y==n-1){
solArr[x][y]=1;
return true;
}
if(isSafe(arr,x,y,n)){
solArr[x][y]=1;
if(ratinMaze(arr,x+1,y,n,solArr)){
return true;
}
if(ratinMaze(arr,x,y+1,n,solArr)){
return true;
}
solArr[x][y]=0; //backtracking
return false;
}
return false;
}
int main(){
int n;
cin>>n;
int** arr= new int*[n];
for(int i=0;i<n;i++){
arr[i]=new int[n];
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>arr[i][j];
}
}
int** solArr= new int*[n];
for(int i=0;i<n;i++){
solArr[i]=new int[n];
for(int j=0;j<n;j++){
solArr[i][j]=0;
}
}
if(ratinMaze(arr,0,0,n,solArr)){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<solArr[i][j]<<" ";
}
cout<<endl;
}
}
// 1 0 1 0 1
// 1 1 1 1 1
// 0 1 0 1 0
// 1 0 0 1 1
// 1 1 1 0 1
return 0;
}