//https://leetcode.cn/problems/number-of-enclaves/
//飞地的数量
class Solution {
public:
    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};

    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        vector<vector<int>> flag(m,vector<int>(n,0));
        queue<pair<int,int>> q;

        int ret = 0;
        //int count = 0;

        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j] == 1)
                    ret++;
            }
        }


        for(int i = 0; i < m; ++i)
        {
            if(grid[i][0] == 1)   {q.push({i,0});   flag[i][0] = 1;  ret--; }
            if(grid[i][n-1] == 1 && flag[i][n-1] != 1) {q.push({i,n-1}); flag[i][n-1] = 1; ret--;}
        }

        for(int i= 0; i < n; ++i)
        {
            if(grid[0][i] == 1 && flag[0][i] != 1)   {q.push({0,i});   flag[0][i] = 1;   ret--;}
            if(grid[m-1][i] == 1 && flag[m-1][i] != 1) {q.push({m-1,i}); flag[m-1][i] = 1; ret--;}
        }

        cout << ret << endl;
        while(q.size())
        {
            auto [a,b] = q.front();
            q.pop();
            for(int i = 0; i < 4;  ++i)
            {
                int x = a+dx[i];
                int y = b+dy[i];
                if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && flag[x][y] != 1)
                {
                    q.push({x,y});
                    flag[x][y] = 1;
                    ret -= flag[x][y];
                }
            }
        }
        // for(int i = 0; i < m; ++i)
        // {
        //     for(int j = 0; j < n; ++j)
        //     {
        //         if(flag[i][j] == 1)
        //             count++;
        //     }
        // }
            
        //return ret-count;
        return ret;
    }
};

//https://leetcode.cn/problems/map-of-highest-peak/
//地图中的最高点
class Solution {
public:
    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int m = isWater.size();
        int n = isWater[0].size();

        vector<vector<int>> heigh(m,vector<int>(n,-1));
        queue<pair<int,int>> q;

        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; ++j)
                if(isWater[i][j] == 1)
                {
                    q.push({i,j});
                    heigh[i][j] = 0;
                }
         
         while(q.size())
         {
            auto [a,b] = q.front();
            q.pop();
            for(int i = 0; i < 4; ++i)
            {
                int x = a+dx[i];
                int y = b+dy[i];
                if(x >= 0 && x < m && y >= 0 && y < n && heigh[x][y] == -1)
                {
                    q.push({x,y});
                    heigh[x][y] = heigh[a][b]+1;
                }
            }
         }

         return heigh;
    }
};