什么是绘制白板作为输入的有效算法

Question

有一块M x N(M，N <= 50)板，它被分成多个单元正方形。每个单元正方形都被涂成白色。我试着把一些空格涂成黑色。绘画意味着选择连续的白色方块(水平笔触或一个垂直笔触)并将它们涂成黑色。在连续的白色方块中使用水平笔划和垂直笔划的组合，找到最小数量的绘画。

我试着解决它，但我找不到一个可能的解决方案。现在，我想知道有效的算法来解决这个问题。

exam1)

给定一个5x3矩阵作为问题输入，

'o‘->黑色

'x‘->白色

O o o

X o x

O o o

X o x

O o o

答案)绘画的最小数量是5。

绘制(0,0 ... 0,2)

绘制(2,0 ... 2,2)

绘制(4,0 ... 4,2)

绘制(1,1)

绘制(3,1)

exam2)

给定一个3x3矩阵，

O x o

O o o

O x o

答案)绘画的最小数量是3。

绘制(0,0 ... 2,0)

绘制(1,1)

绘制(0，2...2)

exam3)

给定一个3x3矩阵，

O o o

O o o

O x o

答案)绘画的最小数量是3。

绘制(0,0 ... 2,0)

绘制(0,1 ... 1,1)

绘制(0，2...2)

exam4)

给定一个3x3矩阵，

O x o

X o o

O x o

答案)绘画的最小数量是4。

绘制(0，2...2)

绘制(0,0)

绘制(1,1)

绘制(2,0)

Answer 1

要做到这一点，一种方法是遍历可能性，在每次执行操作时进行计数，并取count的最小值。

f(grid,count)
    for each square in grid
        if square is a circle // i.e. 'o'
            return min(g(grid with vertical stroke,count+1),
                       g(grid with horizontal stroke,count+1))
    return count

我代表

o o o
x o x
o o o
x o x
o o o

通过

boolean arr [][] = {
            {false,false,false},
            {true,false,true},
            {false,false,false},
            {true,false,true},
            {false,false,false}
    };

在java中，我有：

// return copy of arr
static boolean[][] copy(boolean arr[][]){
    boolean[][] c = new boolean[arr.length][arr[0].length];
    for(int i = 0; i < arr.length; i++)
        c[i] = arr[i].clone();
    return c;
}

// select consecutive squares horizontal stroke at (i,j)
static boolean[][] leftRight(boolean arr[][],int i, int j){
    boolean[][] c = copy(arr);

    // right
    int k = j;
    while (true){
        if(k==arr[0].length || c[i][k]){
            break;
        }
        c[i][k] = true;
        k++;
    }

    // left
    k = j;
    while (true){
        if(k==-1 || c[i][k]){
            break;
        }
        c[i][k] = true;
        k--;
    }
    c[i][j] = true;
    return c;
}

// select consecutive squares vertical stroke at (i,j)
static boolean[][] upDown(boolean arr[][],int i, int j){
    boolean[][] c = copy(arr);

    // down
    int k = i;
    while (true){
        if(k==arr.length || c[k][j]){
            break;
        }
        c[k][j] = true;
        k++;
    }

    // up
    k = i;
    while (true){
        if(k==-1 || c[k][j]){
            break;
        }
        c[k][j] = true;
        k--;
    }
    c[i][j] = true;
    return c;
}


static int g(boolean arr[][], int count){
    // for each square in grid
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr[0].length; j++) {
            // if false then select square
            // and try horizontal and vertical stroke
            // take the min of the 2
            if (!arr[i][j]) {
                return Math.min(g(leftRight(arr,i,j),count+1),g(upDown(arr,i,j),count+1));
            }
        }
    }
    return  count;
}


public static void main(String args[]){
    /*
    o o o
    x o x
    o o o
    x o x
    o o o
    */
    boolean arr [][] = {
            {false,false,false},
            {true,false,true},
            {false,false,false},
            {true,false,true},
            {false,false,false}
    };
    System.out.println(g(arr,0));

}

输出：

5