1
\$\begingroup\$

Problem: We have a two dimensional matrix of positive integer cells. On each turn any non-zero cell with a neighbor (top/bottom/left/right) of zero decreases by 1. We want count to the number of non-zero cells present and add them up across all turns.

Is there a faster solution than to use a priority queue?

Is there a name for this problem or a similar problem? I don’t know what to search for.

Example

Here is an input where the result is 7:

00000
00100
01210
00100
00000

Initially there are 5 non-zero cells.

00000
00000
00200
00000
00000

After the first turn, there is 1 non-zero cell.

00000
00000
00100
00000
00000

After the second turn, there is still 1 non-zero cell.

00000
00000
00000
00000
00000

After the third turn, there are 0 non-zero cells.

If we total these up:

\$5 + 1 + 1 = 7\$

Our result is \$7\$

\$\endgroup\$

closed as off-topic by Adám, Sriotchilism O'Zaic, nimi, lirtosiast, Luis Mendo Jul 7 at 22:35

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This site is for programming contests and challenges. General programming questions are off-topic here. You may be able to get help on Stack Overflow." – Adám, nimi, Luis Mendo
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    \$\begingroup\$ Welcome to CGCC! "Is there a faster solution than to use a priority queue?", "Is there a name for this problem or a similar problem?" - this is not the right stack for these questions as we host competitive programming problems. This might fit here as a challenge, although I'm not 100% sure, but if you're after answers to those questions you might not find them here. As far as I can tell though it seems to be a cellular automaton related to an Abelian sandpile. \$\endgroup\$ – Jonathan Allan Jul 7 at 20:06
  • 1
    \$\begingroup\$ Also wouldn't the example answer be 3 since the four 1s all decrease to 0 at the same time-step? \$\endgroup\$ – Jonathan Allan Jul 7 at 20:11
  • \$\begingroup\$ The problem is totaling the time each cell takes to reach zero. Each of the ones were 1, so 4 x 1. \$\endgroup\$ – LFA Jul 7 at 20:39
  • \$\begingroup\$ Welcome to the site! Like Johathan Allen I am not sure on what the desired task is, or where the number 7 comes from in your example. If you could explain the task without using examples first and then add one or two examples. Then we could move forward to seeing if there is an on topic challenge that can be made from this. In the meanwhile you should checkout the help center. Ideally you should also move this to the sandbox where it can get the help it needs to be on topic. \$\endgroup\$ – Sriotchilism O'Zaic Jul 7 at 21:01
  • 1
    \$\begingroup\$ This can make a good challenge, but you need a winning criterion. code-golf could work, or once you find out the fastest algorithm by asking on CS.SE or Stack Overflow, code-golf restricted-complexity restricting answers to use an algorithm of that time complexity. \$\endgroup\$ – lirtosiast Jul 7 at 22:23

Browse other questions tagged or ask your own question.