Funky chess board hints

#1

need some hints to apprach the problem

1 Like
#2

Hello @Divya_321

THE PROBLEM STATEMENT
The question simply asks you to print the number of cells that the knight cannot reach starting from upper left most cell on chessboard.
Here the knight can pass (NOT STOP) over empty space.

Example Test case
4
1 1 1 0
0 0 1 1
0 0 0 1
1 1 1 1

Here the 1’s in the cell indicate that it is a part of the chessboard and the knight can stop/rest/visit this cell while 0’s indicate that these cells are NOT the part of the chessboard, the knight can only pass over them but cannot stop/rest/visit them.

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.

If you need any help, leave a reply to this thread and I will get back to you.

3 Likes
#3

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.

#4

code link: https://pastebin.com/E7QuuTWG

I have done as you said and according to me it’s working right but it’s wa so please correct it.

#5

Hello @Divya_321

In this problem the knight cannot visit an index again.
Example
3
1 0 0
0 0 1
0 1 0

correct output: 1

explanation
Starting from (0, 0) we can either go to (1, 2) or (2, 1) but after going to either (1, 2) or (2, 1) we cannot come back to (0, 0).
So based on the choice (1, 2) or (2, 1) there can be many different possible answers at the end but we need to print the minimum one (In which minimum number of cells remain unvisited).

In line 53 of your code you should also check if the cell (i, j) is a part of the chess board or Not.
so it would be if(m[i][j] == 1 && check[i][j] != -1)

Also you should initialize a complete matrix with 0 or whatever number you like.
Like I have done with check (memset(check, 0, sizeof(check)))
memset initializes the whole “check” matrix with 0’s

You have a nice coding style. Keep it up !!
Try to solve it now before reading further.

Here is the modified code

Let me know if you still need any help.

2 Likes
#6

1.please explain why you have used this function

void updateMin(int **m) {
int count = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++) {
if (m[i][j] == 1 && check[i][j] != -1)
count++;
}
}
minimum = min(minimum, count);
}

2.use of calling it after marking box visited
3. if(check[i][j]==1) isn’t it means it’s not equals to -1 so why should I add extra condition also I am marking -1 in case of visited and 1 in case it exists as unvisted please explain.

#7

from (0, 0) we can go to (1, 2) or (2, 1)
so in one scenario I will go to (1, 2) and then from (1, 2) to other cells
in another scenario I will go to (2, 1) and then from (2, 1) to other cells

Any scenario can be the best scenario (minimum number cells remain unvisited).
So I am updating the minvalue every time (I am checking the whole board for the cells that are Not visited and updating the min Value)

Also note that it may so happen that if I go to (2, 1) first, then I may Not be able to visit (1, 2) from here onwards.

#8

Example
3 3
1 0 1
0 0 1
0 1 0

If I visit from (0,0) to (1, 2) then from (1, 2) I cannot go anywhere else (I cannot also go back to (0 , 0) because I have already visited once) but if
I visit from (0, 0) to (2, 1) then from (2, 1) I can go to (0, 2) and then nowhere else from here. In this scenario less number of cells remain unvisited and this is the answer.
So I update the minimum value in all the cases to get the best scenario.

I hope that I have cleared your doubt.

#9


input
is
4
on coding block it show error please check this and where it is wrong