将网格划分为几种可能性

Question

大小为m*n的网格仅提供数字1、2、3，其中m是行数，n是列数。

将网格划分为水平或垂直两个部分，这样每个划分必须包含至少一个值为2的单元格。一旦分割，我们可以进一步划分以获得其他组合。查找给定网格值可以划分多少个分区。

例如，如果输入网格：

1,2,3
2,1,2
3,1,1

输出为 4。

下面的是4种可能性。

Possibility (1)
 1,2,3
-------
 2,1,2
 3,1,1
 
  |
2,|1,2
3,|1,1
  |
  
Possibility (2)
  
 1,2,3
-------
 2,1,2
 3,1,1
    
    |
2,1,|2
3,1,|1
    |
Possibility (3)
  |
1,|2,3
2,|1,2
3,|1,1
  |
 
  | 
2,|3
1,|2
1,|1  
  |
  
Possibility (4) 
  |
1,|2,3
2,|1,2
3,|1,1
  |
 
 2,3
-----
 1,2
 1,1 

如何在运行时复杂度方面有效地解决这一问题。

作为第一步，我修改了网格，在元素为1或3时将值设置为0，然后在元素为2时将值设置为1。因此，我将其转换为二进制矩阵。但我无法找到一种可能的组合。

public int process(int[][] grid) {
   int m = grid.length, n = grid[0].length;
   int result = 0;
   for(int i=0; i<m; i++) {
      for(int j=0; j<n; j++) {
         int e = grid[i][j];
         if(e == 2) grid[i][j] = 1;
         else grid[i][j] = 0;
      }
   }
   //.....todo...
   return result;
}

Answer 1

我不太理解你的问题，但这是我的两分钱：

首先，定义一个检查子网格是否包含至少一个2的方法：

public static boolean contains2(int[][] grid, int rs, int re, int cs, int ce) {
    for (int i = rs; i < re; i++) {
        for (int j = cs; j < ce; j++) {
            if (grid[i][j] == 2) {
                return true;
            }
        }
    }
    return false;
}

接下来，您可以定义一个方法，返回子网格中可能的水平拆分数：

public static int splitCountH(int[][] grid, int rs, int re, int cs, int ce) {
    int result = 0;
    for (int i = rs+1; i < re; ++i) {
        if (contains2(grid, rs, i, cs, ce) && contains2(grid, i, re, cs, ce)) {
            ++result;
        }
    }
    return result;
}

另一个给出可能的垂直分裂数：

public static int splitCountV(int[][] grid, int rs, int re, int cs, int ce) {
    int result = 0;
    for (int j = cs+1; j < ce; ++j) {
        if (contains2(grid, rs, re, cs, j) && contains2(grid, rs, re, j, ce)) {
            ++result;
        }
    }
    return result;
}

下一种方法给出了水平分裂、垂直分裂或垂直分割后的水平分裂的可能组合数：

public static int process(int[][] grid, int rs, int re, int cs, int ce) {
    int result = 0;
    for (int i = rs+1; i < re; ++i) {
        if (contains2(grid, rs, i, cs, ce) && contains2(grid, i, re, cs, ce)) {
            result += splitCountV(grid, rs, i, cs, ce)
                    + splitCountV(grid, i, re, cs, ce);
        }
    }
    for (int j = cs+1; j < ce; ++j) {
        if (contains2(grid, rs, re, cs, j) && contains2(grid, rs, re, j, ce)) {
            result += splitCountH(grid, rs, re, cs, j)
                    + splitCountH(grid, rs, re, j, ce);
        }
    }
    return result;
}

您的流程方法如下：

public static int process(int[][] grid) {
    return process(grid, 0, grid.length, 0, grid[0].length);
}

更新：

如果要授权两个水平拆分或两个垂直拆分，可以添加以下方法：

public static int splitCount(int[][] grid, int rs, int re, int cs, int ce) {
    return splitCountH(grid, rs, re, cs, ce)
            + splitCountV(grid, rs, re, cs, ce);
}

并修改process方法：

public static int process(int[][] grid, int rs, int re, int cs, int ce) {
    int result = 0;
    for (int i = rs+1; i < re; ++i) {
        if (contains2(grid, rs, i, cs, ce) && contains2(grid, i, re, cs, ce)) {
            result += splitCount(grid, rs, i, cs, ce)
                    + splitCount(grid, i, re, cs, ce);
        }
    }
    for (int j = cs+1; j < ce; ++j) {
        if (contains2(grid, rs, re, cs, j) && contains2(grid, rs, re, j, ce)) {
            result += splitCount(grid, rs, re, cs, j)
                    + splitCount(grid, rs, re, j, ce);
        }
    }
    return result;
}

但在这种情况下，您将有6种可能性为您的例子。