Rat chase its cheese

#1

sir how this problem get resolves through linkedlist,help plz

#2

@sameeksha,
Not a linked list problem. You can just simple recursion for this

#3

@sameeksha,

  • Bigger Problem : To find any path available from [0, 0] to [N - 1, N - 1].
  • Smaller Problem : Assume the recursion works and will give you ans whether any path exist for positions [cr, cc + 1] to [N - 1, N - 1] or [cr, cc - 1] to [N - 1, N - 1] or [cr - 1, cc] to [N - 1, N - 1] or [cr + 1, cc] to [N - 1, N - 1].
    Self Work : In order to make you smaller prblm your problem all you need to work for the current position by giving 4 calls to these positions.

Note:

  • In order to make sure you donot caught up in infinite recursion by giving 4 calls to every position without checking if we have explored that particular position or not other our recursion will caught up in infnite recursion, we will use a visited boolean 2D array that will account for the position that has been explored.
  • Also we need to backtrack and undo the visited block as we return from the position.
  • Use either by returning true if found solution or declare a global variable in order to check if you have found a path or not.
#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#5

sir now i am getting run error

#6

import java.util.*; public class rat_chases_its_cheese { static Scanner s=new Scanner(System.in); public static void main(String[] args) { int row =s.nextInt(); int column =s.nextInt(); char[][] arr=new char[row][column]; for(int i=0;i<row ;i++) { for(int j=0;j<column ;j++) { arr[i][j] =s.next().charAt(0); } } path(0 ,0 ,row-1,column-1 ,arr); if(arr[row-1][column-1] !=‘1’) { System.out.print(“NO PATH FOUND”); }else { for(int i=0;i<row ;i++) { for(int j=0;j<column ;j++) { if(arr[i][j] == ‘1’) { System.out.print("1 "); }else { System.out.print(“0 “); } } System.out.println(””); } } } public static void path(int inir,int inic,int finr ,int finc ,char[][] arr) { if(inir == finr && inic == finc) { if( arr[inir][inic] ==‘O’ ) { arr[inir][inic] =‘1’; return; }else { return; } }else if(inir == finr && inic != finc) { if( arr[inir][inic] ==‘O’ ) { arr[inir][inic] =‘1’; path(inir ,inic+1 ,finr ,finc ,arr); }else { path(inir-1 ,inic+1 ,finr ,finc ,arr); } }else if(inir != finr && inic != finc) { if( arr[inir][inic] ==‘O’ ) { arr[inir][inic] =‘1’; path(inir+1 ,inic ,finr ,finc ,arr); }else { path(inir-1 ,inic+1 ,finr ,finc ,arr); } } } }

#7

@sameeksha,
Can you please share your code through https://ide.codingblocks.com/