题目来源:100. 岛屿的最大面积
C++题解:
1. 广度优先搜索。使用队列存储,一层一层地往外扩展。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int res = 0, tmp = 0;
int bfs(vector<vector<int>> &grid, vector<vector<int>>&visited, int &tmp, int x, int y){
queue<pair<int, int>> que;
que.push({x, y});
if(visited[x][y]==1 || grid[x][y] == 0) return tmp;
visited[x][y] = true;
tmp = tmp + 1;
if(x-1 > 0) {
if(grid[x-1][y] == 1 && visited[x-1][y] == 0){
que.push({x-1, y});
}
}
if(y-1 > 0) {
if(grid[x][y-1] == 1 && visited[x][y-1] == 0){
que.push({x, y-1});
}
}
if(x+1 < grid.size()) {
if(grid[x+1][y] == 1 && visited[x+1][y] == 0){
que.push({x+1, y});
}
}
if(y+1 < grid[0].size()) {
if(grid[x][y+1] == 1 && visited[x][y+1] == 0){
que.push({x, y+1});
}
}
while(!que.empty()){
pair<int, int> cur = que.front();
que.pop();
int curx = cur.first, cury = cur.second;
tmp = bfs(grid, visited, tmp, curx, cury);
}
return tmp;
}
int main(){
int N, M;
cin >> N >> M;
vector<vector<int>> grid(N+1, vector<int>(M+1, 0));
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++) {
cin>>grid[i][j];
}
}
vector<vector<int>> visited(N+1, vector<int>(M+1, 0));
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++) {
if(visited[i][j] == 1) continue;
tmp = 0;
tmp = bfs(grid, visited, tmp, i, j);
res = max(res, tmp);
}
}
cout<<res;
return 0;
}
2. 深度优先搜索。一个点走到尽头再去找下一个。
#include <iostream>
#include <vector>
using namespace std;
int res = 0, tmp = 0;
int dfs(vector<vector<int>> &grid, vector<vector<int>>&visited, int &tmp, int x, int y){
if(visited[x][y]==1 || grid[x][y] == 0) return tmp;
visited[x][y] = true;
tmp = tmp + 1;
if(x-1 > 0) {
if(grid[x-1][y] == 1 && visited[x-1][y] == 0){
tmp = dfs(grid, visited, tmp, x-1, y);
}
}
if(y-1 > 0) {
if(grid[x][y-1] == 1 && visited[x][y-1] == 0){
tmp = dfs(grid, visited, tmp, x, y-1);
}
}
if(x+1 < grid.size()) {
if(grid[x+1][y] == 1 && visited[x+1][y] == 0){
tmp = dfs(grid, visited, tmp, x+1, y);
}
}
if(y+1 < grid[0].size()) {
if(grid[x][y+1] == 1 && visited[x][y+1] == 0){
tmp = dfs(grid, visited, tmp, x, y+1);
}
}
return tmp;
}
int main(){
int N, M;
cin >> N >> M;
vector<vector<int>> grid(N+1, vector<int>(M+1, 0));
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++) {
cin>>grid[i][j];
}
}
vector<vector<int>> visited(N+1, vector<int>(M+1, 0));
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++) {
if(visited[i][j] == 1) continue;
tmp = 0;
tmp = dfs(grid, visited, tmp, i, j);
res = max(res, tmp);
}
}
cout<<res;
return 0;
}