1293. Shortest Path in a Grid with Obstacles Elimination，417. Pacific Atlantic Water Flow

采用BFS的方法，一个队列里面存放四个数字，前二个时坐标x,y，第三个时结果res,第四个时K，表明再当前坐标下还有几次可以跳过遮挡。一个vector,里面存放的不仅表示是否被访问过，还表示此时的遮挡的次数，要是的此坐标的遮挡次数最大。

class Solution {
public:
    int shortestPath(vector>& grid, int k) {
        int m = grid.size();
        int n = grid[0].size();
        // This vector stores the number of obstacles that we can still remove after walking through that cell
        vector> visited(m, vector(n, -1));
        queue> q;
        // vector> dir = {{0,1}, {0,-1}, {1,0}, {-1,0}};
        // if(grid[0][[0]!=0]) k--;
        q.push({0, 0, 0, k});
        while(!q.empty()){
            auto t = q.front();
            q.pop();
            int x=t[0], y=t[1];
            if(x<0 || x>=m || y <0 || y >=n) continue;
            if(x==m-1 && y == n-1) return t[2];
            // cout<0) t[3]--;
                else continue;
            }
            //保障遮挡的次数最大
            if(visited[x][y]!=-1 && visited[x][y]>=t[3]) continue;
            
            visited[x][y]=t[3];
            
            q.push({x+1, y, t[2]+1, t[3]});
            q.push({x-1, y, t[2]+1, t[3]});
            q.push({x, y+1, t[2]+1, t[3]});
            q.push({x, y-1, t[2]+1, t[3]});
            
        }
        return -1;
    }
};

太平洋的边界是-上边和左边 大西洋的边界时下边和右边，需要找一个某个点，它既可以流到大西洋，也可以流到太平洋，换句话说——流向太平洋 代表这个点正上方或者正左方 单调递减，同理流向大西洋是代表正右方正下方单调递减。即这个点四个方向都单调递减。采用先看横再看竖。只有四边的点比当前点的值小才可以入队，visited才变成true.要同时流向大西洋和太平洋。

class Solution {
public:
    int m, n;
    vector > ans;
    vector > atlantic, pacific;
    queue > q;
    vector > pacificAtlantic(vector>& mat) {
        if(!size(mat)) return ans;
        m = size(mat), n = size(mat[0]);
        atlantic = pacific = vector >(m, vector(n, false));
        for(int i = 0; i < m; i++) bfs(mat, pacific, i, 0), bfs(mat, atlantic, i, n - 1);
        for(int i = 0; i < n; i++) bfs(mat, pacific, 0, i), bfs(mat, atlantic, m - 1, i);             
        return ans;
    }
    void bfs(vector >& mat, vector >& visited, int i, int j){        
        q.push({i, j});
        while(!q.empty()){
            tie(i, j) = q.front(); q.pop();
            if(visited[i][j]) continue;
            visited[i][j] = true;
            if(atlantic[i][j] && pacific[i][j]) ans.push_back(vector{i, j});
            if(i + 1 <  m && mat[i + 1][j] >= mat[i][j]) q.push({i + 1, j});
            if(i - 1 >= 0 && mat[i - 1][j] >= mat[i][j]) q.push({i - 1, j});
            if(j + 1 <  n && mat[i][j + 1] >= mat[i][j]) q.push({i, j + 1});
            if(j - 1 >= 0 && mat[i][j - 1] >= mat[i][j]) q.push({i, j - 1});
        }
    }
};