Here is the problem's link : http://codeforces.me/contest/877/problem/D
In this problem I used BFS to solve it. In my WA submission I choose to break when the distance from the origin of the cell I am traversing is smaller or equal to the distance of the point of the front of the queue plus 1. In my accepted solution I choose to break when the distance from the origin of the cell I am traversing is smaller or equal to the distance of the point of the front of the queue. But I can't understand why my first solution fail. Can anyone give me the explanation ?
Correct : http://codeforces.me/contest/877/submission/31687084 WA: http://codeforces.me/contest/877/submission/31686998
Auto comment: topic has been updated by coding_weeb (previous revision, new revision, compare).
Auto comment: topic has been updated by coding_weeb (previous revision, new revision, compare).
Undefined behaviour.
xx + ican be greater than array size.I have already taken care of that situation by creating a border around the original array.
Ah, sorry. Let
k = 3, xx = 3, yy = 3, dist[3][3] = 5, dist[4][3] = 6, dist[5][3] = INF. This situation is possible, if you have already been inxx = 4, yy = 2anddist[4][2] = 5. You have to changedist[xx + 2][yy], but with+1your code breaks.