岛屿的最大面积
. - 力扣(LeetCode)
1.刚开始mn又加了int
2.bfs里符合条件了,不push,,,在写什么几把
class Solution {
public:int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};bool vis[50][50];int m, n;int maxAreaOfIsland(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();int ret = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] && !vis[i][j]){ret = max(ret, bfs(grid, i, j));}}}return ret;}int bfs(vector<vector<int>>& grid, int i, int j){queue<pair<int, int>> q;q.push({i, j});vis[i][j] = true;int count = 1;while(q.size()){auto e = q.front(); q.pop();for(int i = 0; i < 4; i++){int x = e.first + dx[i], y = e.second + dy[i];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] && !vis[x][y]){count++;q.push({x, y});vis[x][y] = true;}}}return count;}
};
被围绕的区域
. - 力扣(LeetCode)
就是需要对外圈进行标记,一种是改变原来的值,最后在变回来,另一种是vis进行标记,
class Solution {
public:int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n;void solve(vector<vector<char>>& board) {m = board.size(), n = board[0].size();// for(int i = 0; i < n; i++)// dfs(board, 0, i), dfs(board, m - 1, i);// for(int i = 0; i < m; i++)// dfs(board, i, 0), dfs(board, i, n - 1);for(int i = 0; i < n; i++){if(board[0][i] == 'O') bfs(board, 0, i);if(board[m - 1][i] == 'O') bfs(board, m - 1, i);}for(int i = 0; i < m; i++){if(board[i][0] == 'O') bfs(board, i, 0);if(board[i][n - 1] == 'O') bfs(board, i, n - 1);}for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(board[i][j] == 'O') board[i][j] = 'X';else if(board[i][j] == ' ') board[i][j] = 'O';}}}void bfs(vector<vector<char>>& board, int i, int j){queue<pair<int, int>> q;q.push({i, j});board[i][j] = ' ';while(q.size()){auto e = q.front(); q.pop();for(int i = 0; i < 4; i++){int x = e.first + dx[i], y = e.second + dy[i];if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O'){board[x][y] = ' ';q.push({x, y});}}}}
};