將白板作爲輸入的有效算法是什麼

將M×N（M，N < = 50）板劃分爲單位正方形。每個單位的正方形都塗成白色。我試圖畫一些黑色的空間。繪畫意味着選擇連續的白色方塊（水平筆劃或垂直筆劃）並將它們塗成黑色。在連續的白色方塊中使用水平筆畫和垂直筆畫的組合，可以找到最少的繪畫數量。將白板作爲輸入的有效算法是什麼

我試圖解決它，但我找不到一個可能的解決方案。現在，我想知道解決它的有效算法。

exam1）
給定一個5×3矩陣作爲問題輸入，
'O' - >黑
'X' - >白

OOO
XOX
OOO
XOX
OOO

answer）繪畫的最小數量是5.
漆（0,0 ...... 0,2）
塗料（2,0 ...... 2,2）
塗料（4,0 ...... 4,2）
塗料（1,1）
塗料（3,1）

exam2）
給定一個3×3矩陣，

氧代
OOO
氧代

答案）畫的最小數爲3
漆（0,0 ...... 2,0）
塗料（1,1）
塗料（0,2 ...... 2,2）

exam3）
給定一個3×3矩陣，

OOO
OOO
氧代

回答）畫的最小計數爲3
漆（0,0 ...... 2,0）
塗料（0,1 ...... 1,1）
塗料（0,2 ...... 2,2）

exam4）
給定一個3×3矩陣，

氧代
白葉枯病
氧代

回答）畫的最小計數是4
塗料（0,2 ...2,2）
塗料（0,0）
塗料（1,1）
漆（要做到這一點2,0）

來源

2016-11-06 Changwon Choe

您的問題描述似乎並沒有與任何你的例子是一致的。你能解釋你的例子嗎？ –

這個問題可以通過說*「只使用純水平和垂直筆劃的組合，在網格中的所有零點上繪製的筆畫的最小數量是多少？」來更好地理解。當然，不要畫'x'。 –

謝謝。更新我的帖子。它好一點。 –

一種方式是經過準備，每次瓶坯的計時動作，並採取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

來源

2016-11-07 17:56:11

Thx。過一會兒，我會嘗試。 –

將白板作爲輸入的有效算法是什麼

回答

相關問題