Rat chases its cheese

#1

Unable to solve Testcase 3
Please Help.

import java.util.*;

public class Main {

public static void main(String args[]) {

Scanner in = new Scanner(System.in);

	int n = in.nextInt(), m = in.nextInt();

	char Maze[][] = new char[n][m];
	in.nextLine();

	for (int i = 0; i < n; i++){
		String str = in.nextLine();
		for(int j =0;j<str.length();j++)
			Maze[i][j] = str.charAt(j);
	}
	boolean ans[][] = new boolean[n][m];
	isItSafe(Maze, ans, 0, 0);
	System.out.println("NO PATH FOUND");
}

public static void isItSafe(char[][] Maze, boolean ans[][], int i, int j) {

	if (i < 0 || j < 0 || i == Maze.length || j == Maze[i].length)
		return;

	if (i == Maze.length - 1 && j == Maze[i].length - 1) {
		if(Maze[i][j]=='X'){
			System.out.println( "NO PATH FOUND");
			System.exit(0);
		}
		else {
			ans[i][j] = true;
			for (int k = 0; k < Maze.length; k++) {
				for (int l = 0; l < Maze[i].length; l++) {
					if (ans[k][l] == true)
						System.out.print("1 ");
					else
						System.out.print("0 ");
				}
				System.out.println();
			}
			System.exit(0);
		}
		return;
	}

	if (Maze[i][j] == 'X'||ans[i][j] == true)
		return;


		ans[i][j] = true;
		// top
		isItSafe(Maze, ans, i - 1, j);

		// bottom
		isItSafe(Maze, ans, i + 1, j);

		// right
		isItSafe(Maze, ans, i, j + 1);
                    // left
		isItSafe(Maze, ans, i, j - 1);
		
		ans[i][j] = false;

}

}

#2

Hey @Yuvraj_Luhach
try for this input
5 7
OOOOOOO
XOXOOXO
OOXXXXX
XOOOOXX
XXOXOOO
you are getting
ArrayIndexOutOfBoundsException

#3

No I am getting the correct answer for it on my Pc

#4

I can’ t pass Testcase 3 please tell what it is its showing ““run error””

#5

import java.util.*;

public class Main {
static boolean if_posible = false;

public static void main(String args[]) {

	Scanner in = new Scanner(System.in);

	int n = in.nextInt(), m = in.nextInt();

	char Maze[][] = new char[n][m];
	// in.nextLine();

	for (int i = 0; i < n; i++) {
		String str = in.next();
		for (int j = 0; j < str.length(); j++)
			Maze[i][j] = str.charAt(j);
	}
	boolean ans[][] = new boolean[n][m];
	isItSafe(Maze, ans, 0, 0);
	if (!if_posible)
		System.out.println("NO PATH FOUND");
}

public static void isItSafe(char[][] Maze, boolean ans[][], int i, int j) {

	if (i < 0 || j < 0 || i == Maze.length || j == Maze[i].length)
		return;

	if (i == Maze.length - 1 && j == Maze[i].length - 1) {
		ans[i][j] = true;
		for (int k = 0; k < Maze.length; k++) {
			for (int l = 0; l < Maze[i].length; l++) {
				if (ans[k][l] == true)
					System.out.print("1 ");
				else
					System.out.print("0 ");
			}
			System.out.println();
		}
		if_posible = true;

return;
}

	if (Maze[i][j] == 'X')
		return;
	Maze[i][j] = 'X';
	ans[i][j] = true;

	isItSafe(Maze, ans, i, j-1);


	isItSafe(Maze, ans, i, j+1);


	isItSafe(Maze, ans, i+1, j );
	
	isItSafe(Maze, ans, i-1, j);
	Maze[i][j] = 'O';
	ans[i][j] = false;

}

}

#6

But it will show wrong answer for–> 5 4 OXOO OOOX XOXO XOOX XXOX – here the point where we want to reach is blocked.

#7

import java.util.*;

public class Main {
static boolean if_posible = false;

public static void main(String args[]) {

	Scanner in = new Scanner(System.in);

	int n = in.nextInt(), m = in.nextInt();

	char Maze[][] = new char[n][m];
	// in.nextLine();

	for (int i = 0; i < n; i++) {
		String str = in.next();
		for (int j = 0; j < str.length(); j++)
			Maze[i][j] = str.charAt(j);
	}
	boolean ans[][] = new boolean[n][m];
	isItSafe(Maze, ans, 0, 0);
	if (!if_posible)
		System.out.println("NO PATH FOUND");
}

public static void isItSafe(char[][] Maze, boolean ans[][], int i, int j) {

	if (i < 0 || j < 0 || i == Maze.length || j == Maze[i].length)
		return;
	
	if (i == Maze.length - 1 && j == Maze[i].length - 1) {
		if (Maze[i][j] == 'X')
			return;
		ans[i][j] = true;
		for (int k = 0; k < Maze.length; k++) {
			for (int l = 0; l < Maze[i].length; l++) {
				if (ans[k][l] == true)
					System.out.print("1 ");
				else
					System.out.print("0 ");
			}
			System.out.println();
		}
		if_posible = true;
		return;
	}
	if (Maze[i][j] == 'X')
		return;
	
if(Maze[i][j] == 'O') {
	Maze[i][j] = 'X';
	ans[i][j] = true;

	isItSafe(Maze, ans, i, j-1);


	isItSafe(Maze, ans, i, j+1);


	isItSafe(Maze, ans, i+1, j );
	
	isItSafe(Maze, ans, i-1, j);
	Maze[i][j] = 'O';
	ans[i][j] = false;
}
}

}

#8

Thanks for the help Sir.

#9

@Yuvraj_Luhach
Please mark your doubts as resolved in your course’s.