查找矩阵中相邻数字的最大面积

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您可以继续使用其他（也可能是相邻的）元素进行搜索。希望我已经清楚了......