Rat chases its Cheese

#1

question link is :- https://hack.codingblocks.com/contests/c/537/570
please tell me where i am wrong
my code is :-
#include<bits/stdc++.h>
using namespace std;

bool ratInMaze(char maze[10][10],int soln[10][10],int i,int j,int n,int m){
if(i==n&&j==m){
soln[n][m]=1;

for(int i=0;i<=n;i++){
    for(int j=0;j<=m;j++){
        cout<<soln[i][j]<<" ";
    }
    cout<<endl;
}        

    return true;
}

if(i>n||j>m){
    return false;
}

if(maze[i][j]=='X'){
    return false;
}

soln[i][j] = 1;

bool right = ratInMaze(maze,soln,i,j+1,n,m);
bool down = ratInMaze(maze,soln,i+1,j,n,m);
bool left = ratInMaze(maze,soln,i,j-1,n,m);
bool up = ratInMaze(maze,soln,i-1,j,n,m);

soln[i][j] = 0;

if(right||down||left||up){
    return true;
}
return false;

}

int main() {
int n,m;
cin>>n>>m;

char maze[10][10];

for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        cin>>maze[i][j];
    }
}

int soln[10][10]={0};

bool ans = ratInMaze(maze,soln,0,0,n-1,m-1);

if(ans==false){
    cout<<"PATH NOT FOUND";
}

return 0;

}

1 Like
Run-Error in rat chase its cheese problem
#2

you are moviing in a infinite loop .
Let say

00X
00X
XXX
answer should be NO PATH.

at index (0,0)
you move down then
at (1,0) right then
at(1 ,1) up then
at (0,1) left
now will again at (0,0) and you will be in infinite loop.

Hit like if u get this problem.

2 Likes
#3

You are correct but here I wants to go in such a manner that if anyone of the 4 statements is correct then it should follow that path so can you tell me what to for that?

1 Like
#4

For moving to a point (i,j) if solution[i][j]=1 it means you already have this node in your path so don’t go to that point
So in your code check value of solution for that point before going to that point

…
.
.
.
.
.
.
.
.
.
.
.
let say at (0,0) first make solution [0][0]=1
now check if solution of downward is 0 then move downward otherwise dont move
now you are at (1,0)
now check if solution of right point is 0 then move right otherwise dont move
now you are at (1,1)
now check if solution of upward is 0 them move upward otherwise dont move
now you are at (0,1)
now check if left is 0 bt u have already make solution[0][0]=1 so dont move .
In this way you can stop infinite loop.

HIT like if u get it

3 Likes
#5

is going in up,down,left,right directions should be in some fixed order , does it make a difference
I am getting no output and wrong answer for one testcases, my code is:-
https://ide.codingblocks.com/s/42540

1 Like
#6

It is not mandatory to choose a specific direction…
.

.
.
…
.
you are not checking whether initial or ending point is blocked or not.

Hit like if u get it

3 Likes
#7

Hey bro …you are printing “PATH NOT FOUND”.
but in question it is written that you have to write “NO PATH FOUND”

Hit like if u get it .

3 Likes
#8

thanks, fianlly i got the 100 score forf this problem

1 Like