ホワイトボードを入力として塗りつける効果的なアルゴリズム

Question

単位の四角に分割されたM×N（M、N < = 50）のボードがあります。各単位の正方形は白く塗られています。私はいくつかのスペースを黒く描こうとします。ペインティングとは、連続する白い四角形（水平ストロークまたは1つの垂直ストローク）を選択して黒塗りをすることを意味します。連続した白い四角で水平ストロークと垂直ストロークの組み合わせを使用して、最小の絵画数を見つけます。

私は解決しようとしましたが、解決策を見つけることができませんでした。さて、私はそれを解決するための効果的なアルゴリズムを知りたい。問題の入力、
'O' として5×3行列を考える

exam1）
- >ブラック
'X' - >白

OOO
XOX
OOO
XOX
OOO

答え）絵画の最小数は5です。
塗料（0,0 ... 0,2）
塗料（2,0 ... 2,2）
塗料（4,0 ... 4,2）
塗料（1,1） 3x3の行列が与えられる
塗料（3,1）

exam2）
、

オキソ
OOO
オキソ

答え）絵画の最小数は3
塗料（0,0 ... 2,0）
塗料（1,1）
塗料（0,2 ... 2,2）

です絵の3×3行列を考える

exam3）
、

OOO
OOO
オキソ

回答）最小カウント3. 0で 塗料（0,0 ... 2,0）
塗料（0,1 ... 1,1）
塗料（0,2 ... 2,2）

exam4）
3x3の行列を考えると 、

オキソ
xoo
オキソ

答え）絵画の最小数は4
塗料です（0,2 ...2,2）これを行うには
塗料（0,0）
塗料（1,1）
塗料（2,0）

Answer 1

一つの方法は、あなたがプリフォーム毎時間のカウント、可能性を経るですアクションは、と私は

で

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

を表す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 

の分を取りますJavaで

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

私が持っている：

// 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