섬 유형 알고리즘 문제 - letcode 섬의 최대 면적

제목 링크 는 0 과 1 을 포함 하 는 비 공 2 차원 배열 grid 를 지정 합 니 다.
한 섬 은 인접 한 1 (토 지 를 대표 하 는 것) 로 구 성 된 조합 으로 이곳 의 '인접' 은 두 개의 1 이 반드시 수평 또는 수직 방향 에서 인접 해 야 한다 고 요구한다.grid 의 네 가장자리 가 0 (대표 물) 에 둘러싸 여 있다 고 가정 할 수 있 습 니 다.
주어진 2 차원 배열 중 가장 큰 섬 면적 을 찾 아 라.(섬 이 없 으 면 귀환 면적 은 0 이다.)
예시 1:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0] 위 면 에 주어진 행렬 은 6 으로 돌아 가 야 한다.섬 은 수평 이나 수직의 네 방향 만 포함 할 수 있 기 때문에 11 이 아니 라 는 것 을 주의해 야 한다.
예시 2:
[[0, 0, 0, 0, 0, 0, 0, 0] 위 에 주어진 행렬 에 대해 0 을 되 돌려 줍 니 다.
메모: 주어진 매트릭스 grid 의 길이 와 너비 가 50 을 초과 하지 않 습 니 다.

class Solution {
     
public:
    int dfs(vector<vector<int>>& grid, vector<vector<int>>& vis, int x, int y,int rows,int cols, int &rest,int cnt) {
     
        
		//   rest==0
		if (rest == 0) return cnt;
        // cout<
        if(grid[x][y]!=1|| vis[x][y]==1) return cnt;
		//       rest--
		--rest;
		//       
		vis[x][y] = 1;
		//dfs          
		/*
			4    
		*/
		if (x+1<rows && vis[x+1][y]!=1 && grid[x+1][y]==1) {
     
			cnt=dfs(grid, vis, x+1, y, rows, cols, rest,++cnt);
		}

		if (y + 1 < cols && vis[x][y+1] != 1 && grid[x][y+1] == 1) {
     
			cnt=dfs(grid, vis, x, y+1, rows, cols, rest,++cnt);
		}

		if (x - 1 >=0 && vis[x - 1][y] != 1 && grid[x - 1][y] == 1) {
     
            cnt=dfs(grid, vis, x-1, y, rows, cols, rest,++cnt);
		}

		if (y - 1 >=0 && vis[x][y-1] != 1 && grid[x][y-1] == 1) {
     
			cnt=dfs(grid, vis, x, y-1, rows, cols, rest,++cnt);
		}
        return cnt;
	}

    int maxAreaOfIsland(vector<vector<int>>& grid) {
     
        int rest = 0,cnt=0;
		int rows = grid.size();
        if(rows==0){
     
            return 0;
        }
		int cols = grid[0].size();
		
		vector<vector<int>> vis(rows, vector<int>(cols));

		//       rest
		for (int i = 0; i < rows;++i) {
     
			for (int j = 0; j < cols;++j) {
     
				if (grid[i][j] ==1) {
     
					++rest;
				}
			}
		}
		//numIslands       
		for (int i = 0; i < rows; ++i) {
     
			for (int j = 0; j < cols; ++j) {
     
				if (rest == 0) break;
				if (grid[i][j] == 1 && vis[i][j]!=1) {
     
					//           cnt++;
					cnt=max(cnt,dfs(grid,vis,i,j,rows,cols,rest,1));
				}
			}
			if (rest == 0) break;
		}
		return cnt;
    }
};