Al-Khwarizmi_Fan's blog

By Al-Khwarizmi_Fan, 2 years ago, In English

You are given a chocolate bar represented as a grid of size $$$N$$$x$$$M$$$, find the number of ways you can finish the chocolate bar by eating it.

When eating the chocolate bar, each time, you remove one block from the grid which is not surrounded by another chocolate block which has not been eaten yet from all 4 directions

Example : Consider the $$$3$$$x$$$3$$$ chocolate bar below, corners colored in Dark Brown and the center in Red, every chocolate block is accessible to be eaten in the very beginning except the center, it becomes accessible if at least on the corners was eaten

What is the best complexity that can be achieved in terms of $$$N, M$$$? and how?

Edit : Sorry for not mentioning that, but the best solution I have came up with myself so far is bitmask dp in $$$O(N*M*(2^{(N*M)}))$$$

  • Vote: I like it
  • +42
  • Vote: I do not like it

| Write comment?
»
13 months ago, # |
Rev. 3   Vote: I like it -9 Vote: I do not like it

edit: mistake.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I don't think the two problems are the same...