we will choose the other diagonal. we maintain visited at each cell for both left and right diagonals
Ok, so if we encounter any cell which is white in dfs, we need to check whether we already did dfs(visited) on this or not, despite whatever the configration of the matrix currently is?
yes
i think it’s better not to change the contents of the matrix. because we have the initial colour and number of flips. anyhow it all comes under the implementation part.
I am not getting the intuition that, lets we have arrive a vertex(W) (Currently not visited before) and did dfs on it, which will essentially change the configuration of the whole matrix. Now, lets say after doing some more dfs, we arrive at same vertex again(it got White again due to some other flipping of diagonal). But since, current configuration is different, we might get the result by doing just one more flip(as now configuration is changed)
That’s right. So we just try both paths and return the minimum?
yeah
Do you agree that we can flip the colour of a current cell only in two ways either left or right. retain the colour in two ways both or none.
yeah, I mean if current cell is white, we can flip its colour either by flipping left or right diagonal. Wht do you meant, by retain the colour in two ways both or none?
I meant that if we flip both the diagonals or none of the diagonals the colour of the cell doesn’t change.
correct,
so we first pick a white cell and call dfs on one of its diagonals.
calling dfs here means making the diagonal visited on every cell in the diagonal
and if any cell is already black we call dfs on the other diagonal.
to retain its colour
B W B
W B B
B B B
If we pick this diagonal(chose 1,0). meaning, B(2,1) is already black. So we need to call dfs (on one diagonal, here we can’t chose left upwards diagonal as it is alrady visited for this black cell)here to retain its colour, Is that what do you meant?
yes
Thankyou all, I have updated the Solution appraoch above in the problem, if anyone interested.
1 Like
In fact I should thank you for posting such a wonderful question.
1 Like