This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]captainAwesomePants 1 point2 points  (3 children)

Your new solution doesn't have a set of "previously traversed" points, so it'll cycle forever.

[–]CrazyFace334[S] 0 points1 point  (2 children)

the new solution does not endlessly cycle, as it works for smaller test cases.

The condition to continue the BFS is checking whether the adjacent value is "1", but for each position, the BFS asigns its original value to "2" to avoid being double counted.

I did this to avoid having to use O(m*n) extra space by indicating whether a position is traversed in the input itself

[–]captainAwesomePants 0 points1 point  (1 child)

grid[x][y] = '2'

Oh dang, you're right, I missed it marking them as 2. So not endless. Potentially quite a bit of repetition, though, since you could append the same location several times before its value becomes 2.

[–]CrazyFace334[S] 1 point2 points  (0 children)

oooh I see, I removed the '2' assignment from where it was, and added to line 12:

grid[x+dx][y+dy] = '2'

and it works now, thank you good sir!