매트릭스에서 인접한 숫자의 가장 큰 영역 찾기

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 절이 false가 될 요소 (0, 0)로 항상 검색을 시작하므로 tempElementsCount를 재설정하기 전에 당신은 다른 (아마도 인접한) 요소들로 검색을 계속할 수 있습니다. 희망은 내가 충분히 분명 ...