图论第三天

似乎要团建了，我再猫会。我必须参与上团建再走。

130.被围绕的区域

先把外围的O变成A，再把飞地的O变成X，再把外围A变回O

class Solution {
public:int neighbor[4][2] ={1,0,0,-1,-1,0,0,1};void solve(vector<vector<char>>& board) {queue<pair<int,int>>que;int n = board.size();int m = board[0].size();for(int i = 0;i < n;i++){if(board[i][0] == 'O')bfs(board,que,i,0,'O','A');if(board[i][m-1] == 'O')bfs(board,que,i,m-1,'O','A');}for(int j = 0;j < m;j++){if(board[0][j] == 'O')bfs(board,que,0,j,'O','A');if(board[n-1][j] == 'O')bfs(board,que,n-1,j,'O','A');}for(int i = 0;i < n;i++){for(int j = 0;j < m;j++){if(board[i][j] == 'O')bfs(board,que,i,j,'O','X');}}for(int i = 0;i < n;i++){for(int j = 0;j < m;j++){if(board[i][j] == 'A')bfs(board,que,i,j,'A','O');}}}void bfs(vector<vector<char>>& board,queue<pair<int,int>>que,int x,int y,char X,char Y){que.push({x,y});board[x][y] = Y;while(!que.empty()){pair<int,int>cur = que.front();que.pop();for(int i = 0;i< 4;i++){int nextx = cur.first + neighbor[i][0];int nexty = cur.second + neighbor[i][1];if(nextx < 0 || nexty < 0 || nextx >= board.size() ||nexty >= board[0].size())continue;if(board[nextx][nexty] == X){board[nextx][nexty] = Y;que.push({nextx,nexty});}}}}
};

417. 太平洋大西洋水流问题

思路：从两边溯流而上。

对不起！！歇一晚上。明天补上。