Wrong ans for test case 0 and 2

#1


Code is running fine for test case 1 but knot for test cases 0 and 2

#2

Hey @Vishu_1801
try for this input
10
1 1 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 0 0 0
0 0 0 0 1 1 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 1 1 0
0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1
correct output 17
your code Gives : 7

#3

Can you please tell me here I went wrong??

#4

import java.util.*;

public class Main {
static int total_visite = 0;

public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int zero = 0;
	int grid[][] = new int[n][n];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			grid[i][j] = sc.nextInt();
			if (grid[i][j] == 1) {
				zero++;
			}
		}
	}

	int nvp = 0;
	// boolean board[][] = new boolean[n][n];
	knightsPlaced(grid, 0, 0, 0);

// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
//
// if (board[i][j] == false) {
// nvp++;
// }
// }
// }
System.out.println(zero - total_visite);

}

public static int knightsPlaced(int grid[][], int row, int col, int visited) {
	if (row >= grid.length || col >= grid[0].length || row < 0 || col < 0 || grid[row][col] == 0) {
		return 0;
	}
	grid[row][col]=0;
	total_visite = Math.max(total_visite, visited+1);
	//board[row][col] = true;
	knightsPlaced(grid, row - 2, col - 1, visited + 1);
	knightsPlaced(grid, row - 2, col + 1, visited + 1);
	knightsPlaced(grid, row - 1, col - 2, visited + 1);
	knightsPlaced(grid, row - 1, col + 2, visited + 1);
	knightsPlaced(grid, row + 1, col - 2, visited + 1);
	knightsPlaced(grid, row + 1, col + 2, visited + 1);
	knightsPlaced(grid, row + 2, col - 1, visited + 1);
	knightsPlaced(grid, row + 2, col + 1, visited + 1);
	grid[row][col]=1;
	return visited;

}

}

#5

Why have you made grid[row][col] = 1 as we are allowed to visit each spot only once ??
And why have you printed zero-total_visite??

#6

@Vishu_1801
Q1. Why have you made grid[row][col] = 1 as we are allowed to visit each spot only once ??
Answer :I have implemented backtracking
this is backtracking concept
total_visite – > maximum number of squares visit .
zero-total_visite – > minimum number of squares that the knight can not reach.