How can i approach this problem

#1

how can i approach this problem???

#2

see the chess board is not placable positions( where nights can be kept) 1 denotes yes knight can be placed , 0 denotes the knight is not placable, invalid position

so the question asks u the maximum no of positions the knight can travell starting from 0,0
u have a dfs call for all 8 possible moves from each cell

Minimize the no of unvisited cells means that knight is able to visit the maximum no of valid positions in the board.
eg:
3
1 1 1
1 1 1
1 1 1
all board positions are 1
so maximum visible cells are 9
now i start the knight from 0,0 have all 8 dfs call at each position
getting to see that knight can move on 8 valid cells at max
hence 9-8 == 1 is the answer
1 cell is left unvisited

#3

I am not able to understand this problem, please suggest any video or explain it

#4

HINT TO SOLVE

  1. Think recursively.
  2. Maintain some other matrix, name it “canBeVisitedMatrix[n][n]”
  3. Initialize this matrix to zero
  4. Search for the very first 1 (upper left most) in the input matrix and from this make recursive calls to
    { (r-2,c-1), (r-2,c+1), (r-1,c-2), (r-1,c+2), (r+1,c-2), (r+1,c+2), (r+2,c-1), or (r+2,c+1) } cells and mark them 1 in our “canBeVisitedMatrix” (These are the vertices which can be visited).
  5. Also make the recursive call for a particular cell only if it is a part of the chessboard.

The cells in our “canBeVisitedMatrix” still marked 0 are the ones that cannot be visited by the knight.