I am still unable to understand how it is 2^D.We are still trying to map a zero cell with every possible available non zero cell. So isn't that still D!
i tried mutisource bfs starting from 0 and reaching the nearest cell having extra stones and 566 / 611 test cases passed can you tell me your apporch why not to apply bfs here
Because it's not greedy, multi source BFS won't guarantee the optimal answer. For example in this matrix: 1 0 2 1 2 1 1 0 1 The optimal result is 2 moves, however with multi source bfs, it might return 3 with this scenario: - Move 1 from cell (1,1) to the cell(0,1) -> cost is 1 - Then move another 1 from the cell(0,2) to the cell(2,1) -> cost is 2 - Then the total cost will be 1+2=3
@@abdalrhmanserag7319thanks for the explanation its really hard for me to come with correct approch the question was giving all the signs to apply bfs here like minimum moves ,matrix acting like weighted graph having all the edge weight equals to 1anyway i know we can try all the permutation but i go with the basic rules and ended up with wrong approch.
I am still unable to understand how it is 2^D.We are still trying to map a zero cell with every possible available non zero cell. So isn't that still D!
Thanks, nice explanation
Out of the box solution!!
Great!
good explanation bro , realy nice one , after seeing your video , i can able to solve in python
Please do a video for the last one. Not able to understand from the discussion. Got the intuition but then saw the constraints 😢
Here you go - th-cam.com/video/dL2QbnqwUx4/w-d-xo.html
i tried mutisource bfs starting from 0 and reaching the nearest cell having extra stones and 566 / 611 test cases passed can you tell me your apporch why not to apply bfs here
Because it's not greedy, multi source BFS won't guarantee the optimal answer. For example in this matrix:
1 0 2
1 2 1
1 0 1
The optimal result is 2 moves, however with multi source bfs, it might return 3 with this scenario:
- Move 1 from cell (1,1) to the cell(0,1) -> cost is 1
- Then move another 1 from the cell(0,2) to the cell(2,1) -> cost is 2
- Then the total cost will be 1+2=3
Wowww
How did u find example that does not work!! 🔥🔥
@@abdalrhmanserag7319thanks for the explanation its really hard for me to come with correct approch the question was giving all the signs to apply bfs here like minimum moves ,matrix acting like weighted graph having all the edge weight equals to 1anyway i know we can try all the permutation but i go with the basic rules and ended up with wrong approch.
bro, can you please share that solution, i want to understand, how can we try multisource bfs on this problem(even if it's not working)
bhai awaj kam hai
Headphone use krle wai
public class solution {
public int minimum move(int [][]grid){
//base case//
int t=0;
for(int i=0;i