Connected Cells in a Grid

출처 : 해커 랭크

난이도 : 중간

알고리즘 : DFS

 

 

각 셀에 다음이 포함된 행렬을 고려하십시오. 0또는 1. 다음을 포함하는 모든 셀 1를 채워진 셀 이라고 합니다 . 두 셀이 수평, 수직 또는 대각선으로 인접해 있으면 서로 연결되어 있다고 합니다 . 다음 표에서 로 표시된 모든 셀은 로 X표시된 셀에 연결되어 있습니다 Y.

XXX
XYX  
XXX    

하나 이상의 채워진 셀이 연결되어 있으면 영역을 형성합니다 . 영역의 각 셀은 해당 영역 내의 0개 이상의 셀과 연결되어 있지만, 반드시 해당 영역의 다른 모든 셀과 직접 연결되어 있는 것은 아닙니다.

주어진 n x m행렬에서 가장 큰 영역 에 있는 세포의 개수를 구하여 출력하세요 . 행렬에는 두 개 이상의 영역이 있을 수 있습니다.

예를 들어, 다음에는 두 개의 지역이 있습니다. 3 x 3매트릭스. 왼쪽 상단의 더 큰 영역에는 다음이 포함됩니다. 3셀. 오른쪽 하단에 있는 작은 셀에는 다음이 포함됩니다. 1.

110
100
001

기능 설명

아래 편집기에서 connectedCell 함수를 완성하세요 .

connectedCell에는 다음과 같은 매개변수가 있습니다.
- int matrix[n][m] : matrix[i]를 나타냅니다 i^th행렬의 행

반환
- int: 가장 큰 지역의 면적

입력 형식

첫 번째 줄에는 정수가 포함됩니다. n, 행렬의 행 수.
두 번째 줄에는 정수가 포함됩니다. m, 행렬의 열 수입니다.
다음 각각은 n라인에 포함됨 m공백으로 구분된 정수 matrix[i][j].

제약 조건

• 0 < n,m < 10

샘플 입력

STDIN       Function
-----       --------
4           n = 4
4           m = 4
1 1 0 0     grid = [[1, 1, 1, 0], [0, 1, 1, 0], [0, 0, 1, 0], [1, 0, 0, 0]]
0 1 1 0
0 0 1 0
1 0 0 0

샘플 출력

5

설명

아래 그림은 행렬의 두 영역을 보여줍니다. 연결된 영역은 X 또는 Y로 채워져 있습니다. 명확성을 위해 0은 점으로 대체되었습니다.

X X . .
. X X .
. . X .
Y . . .

더 큰 지역은 5세포, 표시됨 X.

 

----------------------------------------------------------------------------------------------------------------------------

 

문제 해독

matirx안에서 8방향으로 이동을 가능할때 가장 길게 이어져 있는 선로의 길이를 구하는 문제

 

문제접근

각 matrix의 각 인덱스 지점에서 DFS를 사용하여 경로 길이를 반환

각 8개의 방향으로 움직이기 시작했을때 가장 깊은 선로의 길이를 확인하여 반환

 

public static int connectedCell(List<List<int>> matrix)
    {
        int n = matrix.Count;
        int m = matrix[0].Count;
        bool[,] visited = new bool[n, m];
        int maxSize = 0;
    
        int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
    
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(matrix[i][j] == 1 && !visited[i, j])
                {
                    int size = DFS(i, j, visited, matrix, dx, dy);
                    maxSize = Math.Max(maxSize, size);
                }
            }
        }
    
        return maxSize;
    }

    private static int DFS(int x, int y, bool[,] visited, List<List<int>> matrix, int[] dx, int[] dy)
    {
        int n = matrix.Count;
        int m = matrix[0].Count;
    
        visited[x, y] = true;
        int size = 1;
    
        for(int i = 0; i < 8; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
        
            if(nx >= 0 && nx < n && ny >= 0 && ny < m && 
            matrix[nx][ny] == 1 && !visited[nx, ny])
            {
                size += DFS(nx, ny, visited, matrix, dx, dy);
            }
        }
    
        return size;
    }