i have used backtracking method at every cell of the matrix to check for the occurence of ‘#’ and count it simultaneously and compared the count with the initial no of #.
it can be done simply by using two variables up and down and moving across one column at a time and deciding snake is at down row or up and simultaneously incrementing the number of hashes and when the path is blocked breaking out…if in the end the number of hashes match the number of input hashes one snake is there
Your solution is at least O(n^2), where n <= 10^5, so it is slow. My idea was this:
Find the leftmost ‘#’ . There can be 1 or 2. I try to build the snake from both of them. I try to build a ‘curly’ snake. By this i mean i always try to move up/down and if i cant i go right.
Lets say the board looks like this:
##.###
####.#
I try to build the following two snakes:
03.###
12##.#
12.678
0345.9
Follow the numbers in increasing order starting from 0. As you can see, in the first case the snake gets stuck, but i find a solution in the other case. If neither of the 2 cases can visit all ‘#’ it means no. Otherwise yes.
The idea is kind of intuitive, but i haven’t proven it. Sometimes all you have to do is try an idea and see if it passes :).
2 Likes
yess that’s what i told and did it by same method…it worked in first time…and instead of building 2 snakes keep ways open for both path till you encounter a ‘.’ on your path.
Nice one. My idea was also similar one, and it made the problem quite easy.