java - 编程难题 : how to count number of bacteria that are alive?

Question

最近，我遇到了一个有趣的编程难题，难题中提到了一些曲折。在让我感到惊讶的问题下面，我只是想知道是否有可能在 java 中的任何相关解决方案适用于以下场景。

问题陈述:有一个尺寸为 m*n 的网格，最初，一个细菌出现在网格的左下角单元格 (m-1,0) 中，所有其他单元格都是空的。每一秒后，网格中的每个细菌都会 self split ，并将相邻(水平、垂直和对角线)细胞中的细菌计数增加 1，然后死亡。

n-1 秒后右下角的单元格 (m-1,n-1) 中有多少细菌？我引用了 https://www.codechef.com/problems/BGH17但未能提交解决方案下面是更多问题现场的图片

Answer 1

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;    

public class BacteriaProblem {
      public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Number of Rows: ");
        int m = sc.nextInt();
        System.out.println("Number of Columns: ");
        int n = sc.nextInt();
        int[][] input = new int[m][n];
        input[m - 1][0] = 1;
        Stack<String> stack = new Stack<>();
        stack.push(m - 1 + "~" + 0);
        reproduce(stack, input, n - 1);

        System.out.println("Value at Bottom Right corner after n-1 secs: " + input[m - 1][n - 1]);
      }

      private static void reproduce(Stack<String> stack, int[][] input, int times) {
        //exit condition
        if (times < 1) {
          return;
        }

        //bacteria after splitting
        List<String> children = new ArrayList<>();

        //reproduce all existing bacteria
        while (!stack.isEmpty()) {
          String[] coordinates = stack.pop().split("~");
          int x = Integer.parseInt(coordinates[0]);
          int y = Integer.parseInt(coordinates[1]);


          for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
              if (i == 0 && j == 0) continue;
              split(input, x + i, y + j, children);
            }
          }
          input[x][y]--;
        }

        //add all children to stack
        for (String coord : children) {
          stack.push(coord);
        }

        //reduce times by 1
        reproduce(stack, input, times - 1);

      }

      private static void split(int[][] input, int x, int y, List<String> children) {
        int m = input.length;
        int n = input[0].length;

        if (x >= 0 && x < m && y >= 0 && y < n) {
          input[x][y]++;
          children.add(x + "~" + y);
        }
      }
    }