Java：矩陣中最長的島

嗨我想執行一個代碼，它返回1和1的矩陣中1的島的最大長度。Java：矩陣中最長的島

在1和0的矩陣中，如果矩陣的兩個相鄰元素是1，那麼它們可以形成一個島。矩陣可以有多個島。相鄰元素可以是水平的，垂直的或對角線的。

這裏是邏輯：

import java.util.Arrays; 

public class IslandMatrix { 


    static final int ROW = 5, COL = 5; 
    static int max_1 = 0; 
    public boolean isSafe(int M[][], int row, int col, 
        boolean visited[][]) 
    { 
     if((row >= 0) && (row < ROW) && 
       (col >= 0) && (col < COL) && 
       (M[row][col]==1 && !visited[row][col])){ 
      return true; 
     } 
     return false; 
    } 


    int DFS(int M[][], int row, int col, boolean visited[][]) 
    { 
     max_1 = max_1+1; 
     int rowNbr[] = new int[] {-1, 0, 1, -1, 1, -1, 0, 1}; 
     int colNbr[] = new int[] {-1, -1, -1, 0, 0, 1, 1, 1}; 
     visited[row][col] = true; 
     for (int k = 0; k < 8; ++k) 
      if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited)){ 
       DFS(M, row + rowNbr[k], col + colNbr[k], visited); 
      } 
     return max_1; 
    } 

    int countIsland(int M[][]) 
    { 
     boolean visited[][] = new boolean[ROW][COL]; 
     //int count = 0; 
     int temp = 0; 
     int max =0; 
     for (int i = 0; i < ROW; ++i) 
      for (int j = 0; j < COL; ++j){ 
       max_1 = 0; 
       if (M[i][j]==1 && !visited[i][j]){ 
        temp = DFS(M, i, j, visited); 
        if(temp>max){ 
         max = temp; 
        } 
       } 
      } 
     return max; 
    } 


    public static void main (String[] args) throws java.lang.Exception 
    { 
     int M[][]= new int[][] {{0, 1, 0, 1, 0}, 
           {0, 0, 1, 1, 1}, 
           {1, 0, 1, 1, 0}, 
           {0, 1, 0, 0, 0}, 
           {0, 0, 1, 0, 1} 
           }; 
    IslandMatrix I = new IslandMatrix(); 
    System.out.println("Max length of island is: "+ I.countIsland(M)); 
    } 
}

考慮：

{0, 1, 0, 1, 0} 
{0, 0, 1, 1, 1} 
{1, 0, 1, 1, 0} 
{0, 1, 0, 0, 0} 
{0, 0, 1, 0, 1}

在這種情況下最長的島與1的跟隨如下的指數路徑：（0,1） - >（ 1,2） - >（1,3） - >（0,2） - >（1,4） - >（2,3） - >（2,2） - >（3,1） - >（2 ，0）

以這種方式結果應該是9，但我得到的結果爲10.

任何人都可以用適當的邏輯幫助我。

來源

2017-03-06 kumar

答案不應該是10嗎？（0,1），（0,3），（1,2），（1,3），（1,4），（2,0），（2,2），（2， 3），（3,1），（4,2） – MicD

[爲什麼「有人可以幫我嗎？」不是一個實際的問題？]（http://meta.stackoverflow.com/q/284236/18157） –

有你檢查[算法的這個例子]（http://stackoverflow.com/questions/27736983/count-islands-of-zeros-in-a-matrix?rq=1） –

在這種情況下，您正在使用DFS。它會發現所有連接點不是最長的路徑。結果是10，因爲我們有點落後（3,1）。對於考試，如果您將點（1,0）更改爲1，則結果爲11.

這是主要問題。解決它的代碼將工作。如果你不能，我會幫你。

來源

2017-03-06 07:35:36

是的，即使我看到代碼回溯。我怎樣才能避免這種情況？你能給我一個這個邏輯嗎？ – kumar

Java：矩陣中最長的島

回答

相關問題