目录
130
和昨天的飞地类似，都是从最边缘的位置进行dfs/bfs，然后判断哪个点没有被遍历过
class Solution {
public:
int dir[4][2]={1,0,-1,0,0,1,0,-1};
void dfs(vector<vector<char>>& board,vector<vector<bool>>& visited,int x,int y)
{
for(int i=0;i<4;i++)
{
int nextx=x+dir[i][0];
int nexty=y+dir[i][1];
if(nextx<0||nexty<0||nextx>=board.size()||nexty>=board[0].size())
{
continue;
}
if(!visited[nextx][nexty]&&board[nextx][nexty]=='O')
{
visited[nextx][nexty]=true;
dfs(board,visited,nextx,nexty);
}
}
}
void solve(vector<vector<char>>& board) {
int m=board.size();
int n=board[0].size();
vector<vector<bool>> visited(m,vector<bool>(n,0));
for(int i=0;i<m;i++)
{
if(!visited[i][0]&&board[i][0]=='O')
{
visited[i][0]=true;
dfs(board,visited,i,0);
}
if(!visited[i][n-1]&&board[i][n-1]=='O')
{
visited[i][n-1]=true;
dfs(board,visited,i,n-1);
}
}
for(int j=0;j<n;j++)
{
if(!visited[0][j]&&board[0][j]=='O')
{
visited[0][j]=true;
dfs(board,visited,0,j);
}
if(!visited[m-1][j]&&board[m-1][j]=='O')
{
visited[m-1][j]=true;
dfs(board,visited,m-1,j);
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(!visited[i][j])
{
board[i][j]='X';
}
}
}
}
};
417
还是从两边开始遍历，如果下一个格子的数字比当前的大，那么就说明整体是一个上升的趋势，
如果最后两个visited都有这个格子，就说明是两边都能流到岸边的地方，
class Solution {
public:
int dir[4][2]={1,0,-1,0,0,1,0,-1};
void bfs(vector<vector<int>>& heights,vector<vector<bool>>& visited,int x,int y)
{
queue<pair<int,int>> que;
que.push({x,y});
visited[x][y]=true;
while(!que.empty())
{
auto cur=que.front();que.pop();
for(int i=0;i<4;i++)
{
int nextx=cur.first+dir[i][0];
int nexty=cur.second+dir[i][1];
if(nextx<0||nexty<0||nextx>=heights.size()||nexty>=heights[0].size())
{
continue;
}
if(!visited[nextx][nexty]&&heights[nextx][nexty]>=heights[cur.first][cur.second])
{
visited[nextx][nexty]=true;
que.push({nextx,nexty});
}
}
}
}
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
int m=heights.size();
int n=heights[0].size();
vector<vector<int>> result;
vector<vector<bool>> visitedByPac (m,vector<bool>(n,0));
vector<vector<bool>> visitedByAtl (m,vector<bool>(n,0));
for(int i=0;i<m;i++)
{
if(!visitedByPac[i][0])
{
visitedByPac[i][0]=true;
bfs(heights, visitedByPac, i, 0);
}
if(!visitedByAtl[i][n-1])
{
visitedByAtl[i][n-1]=true;
bfs(heights,visitedByAtl,i,n-1);
}
}
for(int j=0;j<n;j++)
{
if(!visitedByPac[0][j])
{
visitedByPac[0][j]=true;
bfs(heights, visitedByPac, 0, j);
}
if(!visitedByAtl[m-1][j])
{
visitedByAtl[m-1][j]=true;
bfs(heights,visitedByAtl,m-1,j);
}
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(visitedByAtl[i][j]&&visitedByPac[i][j])
{
result.push_back({i,j});
}
}
}
return result;
}
};