Funky chess board

#1

unable to understand problem and sample input, output

#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

1 Like
#3

@chhavibansal thank you for amazing explaination :slightly_smiling_face:
I’ve tried to implement, is this correct way ?


It is not giving correct ans for
0 1 0 0
1 0 1 1
1 1 0 0
0 0 1 1
only (1,0) can’t be visited right? but my code missing (3,2)
I think i m missing backtracking…

#4

check out this code
using backtracking

answer is 8

1 Like
#5

how this code is working?
above example that i gave, in that board[0][0]==0 then first if condition becomes false, then how if condition is working ?

#6

probably no test case covers this condition when 0,0 is 0
the codei provided passes all test cases

#7

ok understood now, thank you

#8

ma’am I have doubt in a question of daily code byte, can i paste here thread link ?

#9

hi @dhairya16 i cannot give a hint the same day
like i can help u out once the contest is over

and u can make a thread too.
i will help u there as well

#10

it is of 2 days ago daily code byte

#11

it would be great if u make a seperate thread.
so that people could refer to it later as well

#12
#13

Hello @chhavibansal ur explaination was good but i am not understanding ur code, why ur using max and why again ur initializing the o=position to 1. My logic is just call for dfs and mark if it and atlast collect all the unmarked ones.
Code link: https://ide.codingblocks.com/s/240759
Please have a look over it. Thank you :slight_smile:

#14

thats because of backtracking

but dude there are many possible ways the knight can move and we are required to tell the one in which no of cells skipped is least
that can be done using backtracking

#15

Still not getting you. or am i confused with ques. Making clear what i had understood from question.
We start from (0,0) and try to reach all the cells possible from there. The moves possible are as knight actually moves in chess. now after moving our knight everywhere( for (0,0) dfs for all moves are returned), we count no. of ones in the matrix. Am i understanding it correct, cause when u replied with shortest move i was flabbergasted.

#16

ab dekh
humne sabse pehle move kahi aur kari out of 8 possible then kahi aur then kahi aur
ab yeh to nhi h na
jo pehli configuration se chala king to usi meh usne maximum cells cover kiye honge
it can be like
uske 2.5 kisi aur direction meh pehle chala then koi aur then koi aur
to hume vo maximum configuration walla batana h
to us case meh kitne min cells unvisited rhe jayegne

jaise yeh chess board h
to isme first move vo 2,1 peh kar sakta h ya 1,2 right ?
to vahi cheese back tracking see hogi
image

1 Like
#17

Broooo, bahot sahin samjati hain reh tu… :heart_eyes: and i now understood the question that we want maximum of all the 8 moves not like evaluating all the moves and than check who is left. Please tell me that’s right. :pleading_face:

1 Like
#18

Ha ree
Like sab position peh tune sab kar karega ki kis position peh ja sakta h knight fir us next position se max ja sakta h
fir uske baad tu max cells visited withing one journey decide kar raha h
to end meh kar diyo total kitne initiallly cell 1 the - jitne max journey meh cover huye

1 Like
#19

thanks. It was the exact thing needed.