class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {

        int n = (int)grid.size();
        int m = (int)grid[0].size();
        int cnt=0;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m;j++)
            {
                if(grid[i][j] == 1)
                {
                   return dfs(i, j, grid);
                }
            }
        }

        return cnt;
    }

    private:
    int dfs(int i, int j, vector<vector<int>>&g )
    {
        if( i< 0 || j < 0 || i >= (int)g.size() || j>= (int)g[0].size())
            return 1;
        if(g[i][j] == 0) return 1;

        if(g[i][j] == -1) return 0;

          int cnt = 0;

        g[i][j] = -1;

        cnt += dfs( i, j+1, g);
        cnt += dfs( i, j-1, g);
        cnt += dfs( i+1, j, g);
        cnt += dfs( i-1, j, g);

        return cnt;

    }
};