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

Question

有一个M x N（M， N

我试图解决它，但找不到可能的解决办法。现在，我想知道解决这个问题的有效算法。

exam1）
给定一个5x3矩阵作为问题输入，
'o'-

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

回答）油漆的最小数量为5<绘制（0,0…0,2）
绘制（2,0…2,2）
绘制（4,0…4,2）
绘制（1,1）
绘制（3,1）

给定一个3x3矩阵，

o x o
o o
o x o

回答）油漆的最小数量为3<绘制（0,0…2,0）
绘制（1,1）
绘制（0,2…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,2)

exam4）
给定一个3x3矩阵，

o x o
x o
o x o

回答）油漆的最小数量为4<绘制（0,2…2,2）
绘制（0,0）
绘制（1,1）
绘制（2,0）

Answer 1

这样做的一种方法是遍历可能性，计算每次预形成一个动作的次数，并计算计数s的最小值

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