calmhandtitan's blog

[Graphs] Snake mask
By calmhandtitan, history, 9 years ago, In English

From quite a long time I was trying to solve this problem 225D - Snake, but I am stuck on how to create a mask for this snake and how to extract information from the mask for doing further BFS.

I referred to I_love_Tanya_Romanova's solution 4086309 for the same, but was unable to understand the magic behind his mask.

So can someone help me understanding how to create mask for this problem.

Many others have used a hash function to solve this problem. I wonder how?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by calmhandtitan (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Your BFS state can be the location (r,c) of the head and a string represents the directions used to go from segment i of the body to the next segment. For example, if the head is at (3,3) and the string = LLU, you know that the grid looks like this:

........
..123...
....4...
........

Again, the string = LLU, this means go Up when you are at 4 and Left when you are at 3 and 2.

You can use set<state> to check if a state (int, int, string) is visited or not, but that's might be slow.

Replace the letters in the string with digits: L = 0, R = 1, U = 2, D = 3, now you have a number in base 4! There are only 8 parents, so the maximum number for a state will be 48 - 1 = 65535.

I think that's the hash function you mentioned, it is the same as saying that we will have two bits for each parent direction, because numbers 0 to 3 need two bits, so the number you will get using hashing is the same as the number you will get using bitmasks.

Here is my solution using hashing: 12162662

→ Reply