マトリックス内の隣接する数字の最大面積を見つける

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 

ここで私はhttp://www.algolist.net/Algorithms/Graph_algorithms/Undirected/Depth-first_searchからDFSの実装を使用して、これまで持っているコードです。すべてのと、数日のためにそれをデバッグした後

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（）メソッドでは、if節が偽になる要素（0、0）で検索を開始するので、tempElementsCountを他の（おそらくは隣接する）要素で検索を続けることができます。私は十分にはっきりしていたと思っています...