class Solution {
public:
    int space;
    int result = 0;
    void dfs(vector<vector<int>>& grid, int i, int j) {
        if(i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != 1) return;
        grid[i][j] = 2;
        space++;
        dfs(grid, i+1, j);
        dfs(grid, i-1, j);
        dfs(grid, i, j-1);
        dfs(grid, i, j+1);
    }

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        for(int i = 0; i < grid.size(); i++) {
            for(int j = 0; j < grid[0].size(); j++) {
                if(grid[i][j] == 1) {
                    space = 0;
                    dfs(grid, i, j);
                    result = max(result, space);
                }
            }
        }
        return result;
    }
};

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        vector<vector<int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int result = 0;

        for(int i = 0; i < grid.size(); i++) {
            for(int j = 0; j < grid[0].size(); j++) {
                if(grid[i][j] == 1) {
                    // start bfs
                    queue<pair<int,int>> que;
                    que.push({i, j});
                    grid[i][j] = 0;     // remember to label visited
                    int space = 1;

                    while(!que.empty()) {
                        auto node = que.front();
                        que.pop();

                        for(auto dir : directions) {
                            int row = node.first + dir[0];
                            int col = node.second + dir[1];

                            if(row < 0 || row >= grid.size() || col < 0 || col >= grid[0].size() || grid[row][col] != 1) {
                                continue;
                            }
                            grid[row][col] = 2;
                            space++;
                            que.push({row, col});
                        }
                    }
                    result = max(result, space);
                }
            }
        }
        return result;
    }
};