[LeetCode] 695. Max Area of Island c++

문제

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

 

배열의 요소 값이 1이고, 1이 상하좌우로 연속되어 있을 때 1의 최대 값을 구하는 문제이다.

 

문제 해결

class Solution {

private:
    int n = 0, m = 0;
    int trav(int i, int j, vector<vector<int>>& grid){
        if(i < 0 || i >= n || j < 0 || j >= m || !grid[i][j]){
            return 0;
        }
        grid[i][j] = 0;
        return 1 + trav(i-1, j, grid) + trav(i+1, j, grid) + trav(i, j-1, grid) + trav(i, j+1, grid);
    }
    
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        
        int ans = 0;
        n = grid.size(), m = grid[0].size();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j]){
                    ans = max( ans, trav(i, j, grid));
                }
            }
        }
        return ans;
    }
};