Trouver la plus grande surface de nombres adjacents dans une matrice

Question

Ceci n'est PAS un devoir. Je suis un débutant en programmation, et c'est aussi mon premier article ici - s'il vous plaît, gardez-moi.

Je n'ai pas réussi à trouver des questions similaires postées ici.

Dans le livre d'un débutant, je trouve la question suivante:

# 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 

Voici le code que j'ai à ce jour, en utilisant la mise en œuvre de DFS http://www.algolist.net/Algorithms/Graph_algorithms/Undirected/Depth-first_search. Il y a « nombres magiques » partout, et les méthodes sont « statique public », etc. - j'avais l'intention de corriger ces choses après l'algorithme travaillé ...

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); 
    } 
} 

Après mise au point pendant plusieurs jours, avec tous les session de débogage le code devient plus compliqué ... toute aide sera appréciée. Merci d'avance.

Answer 1

Je pense que le problème est que vous réinitialisez tempElementsCount à chaque fois. Imaginez comment votre code fonctionnerait sur la matrice donnée et vous verrez que dans la méthode runDFS() vous commencez toujours la recherche avec l'élément (0, 0) pour lequel la clause if sera fausse, donc vous réinitialisez tempElementsCount avant vous pouvez continuer la recherche avec les autres éléments (et probablement adjacents). J'espère avoir été assez clair ...