Divide a grid into several possibilities-CodePudding

A grid of size m*n is provided with numbers 1, 2, 3 only, where m is the number of rows and n is the number of columns.

Divide the grid into two parts either horizontally or vertically such that each division must contain at least one cell with value 2. Once divided we can further divide to get other combinations. Find how many divisions are possible for given grid values.

For example, if the input grid:

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

Output is 4.

Below are the 4 possibilities.

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

How to solve this efficiently in terms of runtime complexity.

As a first step, I have modified the grid by setting the value to 0 when an element is 1 or 3. Then set the value to 1 when an element is 2. So I have converted it to a binary matrix. But I am not able to find a way to get the possible combinations.

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;
}

CodePudding user response：

I'm not sur I understand your question fully, but here are my two cents:

Start by defining a method that checks that a subgrid contains at least one 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;
}

Next, you can define a method returning the number of possible horizontal splits of a subgrid:

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;
}

and another one giving the number of possible vertical splits:

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;
}

Next method gives the number of possible combinations of a horizontal split followed by a vertical split or a vertical split followed by a horizontal split:

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;
}

Your process method becomes:

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

UPDATE:

If you want to authorize two horizontal splits or two vertical splits, you can add the following method:

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);
}

And modify the process method:

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;
}

But in this case, you would have 6 possibilities for your example.

CodePudding user response：

Below are the 4 possibilities.

 (1)    (2)    (3)    (4)

1 2 3  1 2 3  1|2|3  1|2 3
-----  -----   | |    |---
2|1 2  2 1|2  2|1|2  2|1 2
 |        |    | |    |
3|1 1  3 1|1  3|1|1  3|1 1

What about

1 2|3
---| 
2 1|2
   | 
3 1|1