There is this question from codeforces LINK . In case if you have read the problem and solved it already please read along
When I tried to solve this problem I tried to minimize the number of left moves you are required to make to reach to a particular cell because if you think carefully minimizing the left moves automatically reduces the right moves , and this is the exact same strategy given in the editorial of the problem but i got an WA on test case 20 . My submission LINK basically i have just tried to minimize the number of left moves in each step using 0-1 BFS . Any suggestion ? Thanks in advance .
3 Likes
if(it.y+1<m&&arr[it.x][it.y+1]!='*'&&it.r>0&&!vis[it2.fi()][it2.se()])
{
q.push_front(it2);
vis[it2.fi()][it2.se()]=1;
}
It will be push_back not push_front?
AC with push_back
@lamda_cdm_10 The question is very simple once you understand that this problem is just a little variation of breadth first search in a matrix.
Note that, there is only two strategy:-
(1) moving up or down doesn’t have any limit of moving, while
(2) moving left or right limits us to move no more than x and y times respectively to left and right respectively.
Since Breadth first search is divided on the basis of this above two strategy and above (1) strategy should be completed first and then (2) strategy since there might be some case that some cell will be covered only when we traverse up and down any times then go left and right.
Answer:- Use deque instead of queue(for 0-1 BFS) and while pushing elements take care that you should push elements in front for up and down move and push_back() for left and right moves.
Test Case:-
10 15
7 7
7 7
.…*******
…*.*
.…
….
..
.…********.
...…
....********
....********
…*…********
Your Answer:- 52
Correct Answer:- 53
2 Likes
can you just explain why i need to push it to the back instead of pushing it front ? because in this case which you have pointed out i am moving right and in that case no left move is utilized so shouldn’t i push it to the front (because as mentioned by the editorial we are required to minimize the left moves ) ? My whole confusion lies here .