查找矩陣中相鄰數字的最大面積

Question

這不是一項家庭作業。我是編程初學者，這也是我的第一篇文章 - 請耐心等待。

我無法找到這裏發佈的類似問題。

在初學者的書，我發現了以下問題：

# Find the biggest area of adjacent numbers in this matrix: 
1 3 2 2 2 4 
3 3 3 2 4 4 
4 3 1 2 3 3 #--> 13 times '3' 
4 3 1 3 3 1 
4 3 3 3 1 1 

這裏是我到目前爲止的代碼，使用DFS實現從http://www.algolist.net/Algorithms/Graph_algorithms/Undirected/Depth-first_search。有「幻數」無處不在，這些方法是「公共靜態」等等 - 我正打算工作的算法後，以修復這些東西......

public class AdjacentAreaInMatrix { 
    /* 
    * Enums for the state of the Nodes, for use in DFS/BFS 
    */ 
    private enum NodeState { 
     Visited, InProgress, Unvisited 
    }; 

    /* 
    * These 2 'magic' numbers come from the hardcoded 'matrix' below, 
    * cause it has 5 rows and 6 columns 
    */ 
    public static final int ROWSCOUNT = 5; 
    public static final int COLUMNSCOUNT = 6; 

    /* 
    * Two variables for counting the maximum sequence 
    * of numbers (as required by the problem definition) 
    */ 
    private static int tempElementsCount = 0; 
    private static int maxElementsCount = 1; // except if the matrix is empty, then it should be 0 

    /* 
    * The hardcoded matrix 
    */ 
    private static final int[][] matrix = new int[][] { 
      { 1, 3, 2, 2, 2, 4 }, 
      { 3, 3, 3, 2, 4, 4 }, 
      { 4, 3, 1, 2, 3, 3 }, 
      { 4, 3, 1, 3, 3, 1 }, 
      { 4, 3, 3, 3, 1, 1 } }; 

    /* 
    * Create an auxiliary matrix 'state' to implement DFS. 
    * Initialize the whole matrix as 'unvisited' and 
    * start DFS at the first element of the matrix 
    */ 
    public static void DFS() { 
     NodeState state[][] = new NodeState[ROWSCOUNT][COLUMNSCOUNT]; 
     // clear the state of the matrix 
     for (int i = 0; i LT ROWSCOUNT; i++) { 
      for (int j = 0; j LT COLUMNSCOUNT; j++) { 
       state[i][j] = NodeState.Unvisited; 
      } 
     } 
     runDFS(0, 0, state);  
    } 

    /* 
    * Using the auxiliary matrix "state[][]", use DFS to traverse the 
    * 'real' matrix[][] 
    */ 
    public static void runDFS(int i, int j, NodeState state[][]) { 
     state[i][j] = NodeState.InProgress; 
     // traverse the whole matrix state[][] and recursively run runDFS() from the needed elements. 
     for (int rows = 0; rows LT ROWSCOUNT; rows++) { 
      for (int columns = 0; columns LT COLUMNSCOUNT; columns++) { 
       /* 
       * ---------------------------------------------------------------------- 
       * For the logic in the 'if' statement regarding the adjacent elements: 
       * i0j0 i1j0 i1j0 
       * i0j1 i1j1 i2j1 
       * i0j2 i1j2 i2j2 
       * It uses the thing, that the sum of (i+j) for the coordinates of 
       * the elements above, below, on the left and on the right of i1j1 
       * are exactly +1/-1 of the sum of the coordinates of i1j1 
       * -> i1j2 to 1+2 = 3 
       * -> i2j1 to 1+2 = 3 
       * -> i1j1 to 1+1 = 2 (the current element) -> matrix[i][j] 
       * -> i1j0 to 1+0 = 1 
       * -> i0j1 to 1+0 = 1 
       * ---------------------------------------------------------------------- 
       */ 
       if ((matrix[i][j] == matrix[rows][columns]) // if the values are equal 
         && ((((i+j) - (rows + columns)) == 1) || (((i+j) - (rows + columns)) == -1))// and if the element is adjacent 
         && (state[rows][columns] == NodeState.Unvisited)) { // and if the element is still not visited 
        tempElementsCount++; 
        if (tempElementsCount > maxElementsCount) { 
         maxElementsCount = tempElementsCount; 
        } 
        runDFS(rows, columns, state); // recursively run DFS for each element, that "isEdge" 
       } else { 
        // if the elements aren't [adjacent, equal and not visited], start the count again from '0' 
        tempElementsCount = 0; 
       } 
      } 
     } 
     state[i][j] = NodeState.Visited; 
    } 

    public static void go() { 
     AdjacentAreaInMatrix.DFS(); 
     System.out.println(maxElementsCount); 
    } 
} 

調試了好幾天之後，每調試會話代碼變得更加複雜...任何幫助將不勝感激。提前致謝。

Answer 1

我認爲問題在於您每次都重置tempElementsCount。試想一下你的代碼如何在給定的矩陣上工作，你會發現你在runDFS（）方法中總是用元素（0，0）開始搜索，if元素將是false，所以你重置之前tempElementsCount您可以繼續使用其他（也可能是相鄰的）元素進行搜索。希望我已經清楚了......