Flood Filled
深度优先搜索1
C++ 代码
#include <iostream>
using namespace std;
const int N = 1020;
const int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
char g[N][N];
int visit[N][N];
int n;
bool check(int r, int c)
{
for (int k = 0; k < 4; k++) {
int x = r + dir[k][0];
int y = c + dir[k][1];
if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == '.') {
return false;
}
}
return true;
}
void dfs1(int r, int c)
{
for (int k = 0; k < 4; k++) {
int x = r + dir[k][0];
int y = c + dir[k][1];
if (x < 0 || x >= n || y < 0 || y >= n || visit[x][y] || g[x][y] == '.')
continue;
visit[x][y] = 1;
dfs1(x, y);
}
}
void dfs2(int r, int c)
{
g[r][c] = '.';
for (int k = 0; k < 4; k++) {
int x = r + dir[k][0];
int y = c + dir[k][1];
if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == '.')
continue;
dfs2(x, y);
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> g[i][j];
}
}
int ans = 0, cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == '#' && !visit[i][j] && check(i, j)) { //找到一个符合要求的点
cnt++;
visit[i][j] = 1;
dfs1(i, j); //将符合要求的点周围的 # 都标记成true
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == '#') {
ans++; //统计连通岛屿的个数
dfs2(i, j);
}
}
}
cout << ans - cnt << endl;
return 0;
}
深度优先搜索2
C++ 代码
#include <iostream>
using namespace std;
const int N = 1020;
const int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
char g[N][N];
int visit[N][N];
int n;
bool flag = false;
void dfs(int r, int c)
{
visit[r][c] = 1;
int cnt = 0;
for (int k = 0; k < 4; k++) {
int x = r + dir[k][0];
int y = c + dir[k][1];
if (x < 0 || x >= n || y < 0 || y >= n || g[x][y] == '#') {
cnt++;
}
if (g[x][y] == '#' && !visit[x][y]) {
dfs(x, y);
}
if (cnt == 4) {
flag = true;
}
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> g[i][j];
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == '#' && !visit[i][j]) {
flag = false;
dfs(i, j);
if (!flag) {
ans++;
}
}
}
}
cout << ans << endl;
return 0;
}
广度优先搜索
C++ 代码
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1020;
const int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
char g[N][N];
int visit[N][N];
int n;
bool bfs(int r, int c)
{
queue<PII> que;
que.push({r, c});
visit[r][c] = 1;
int sum = 0, bound = 0;
while (!que.empty()) {
PII p = que.front();
que.pop();
sum++;
bool flag = false;
for (int k = 0; k < 4; k++) {
int x = p.first + dir[k][0];
int y = p.second + dir[k][1];
if (x < 0 || x >= n || y < 0 || y >= n || visit[x][y])
continue;
if (g[x][y] == '.') {
flag = true;
continue;
}
que.push({x, y});
visit[x][y] = 1;
}
if (flag) {
bound++;
}
}
return sum == bound;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> g[i][j];
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] == '#' && !visit[i][j]) {
if (bfs(i, j)) { //当前连通块的数量等于周围有海洋的块的数量时,全部被淹没
ans++;
}
}
}
}
cout << ans << endl;
return 0;
}