思路看注释
略了……
dfs
海水+岛屿dfs
直接上代码
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 60;
char d[N][N];
bool st[N][N];
int t, n, m;
int dir8[8][2] = {
{0,1},{0,-1},{1,0},{-1,0},
{-1,-1},{1,-1},{-1,1},{1,1}
};
int dir4[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
void dfsForSea(int x, int y) {
d[x][y] = '2';
for(int i = 0;i < 8;i++) {
int dx = x + dir8[i][0],
dy = y + dir8[i][1];
if (dx < 0 || dx > m + 1 || dy < 0 || dy > n + 1) continue;
if (d[dx][dy] == '0') {
dfsForSea(dx, dy);
}
}
}
void dfsForIsland(int x, int y, bool &flag) {
st[x][y] = true;
if (!flag) { // 每个点扫一次8向 找有没有跟外海相邻
for(int i = 0;i < 8;i++) {
int dx = x + dir8[i][0],
dy = y + dir8[i][1];
if (d[dx][dy] == '2') {
flag = true;
}
}
}
for (int i = 0;i < 4;i++) {
int dx = x + dir4[i][0],
dy = y + dir4[i][1];
if (d[dx][dy] == '1' && !st[dx][dy]) {
dfsForIsland(dx, dy, flag);
}
}
}
int main() {
cin >> t;
while(t--) {
cin >> m >> n;
int cnt = 0;
// 从1开始扫 默认加一层外海 方便我们区分开内海和外海
// 注意被岛和边界半包围因为岛没有形成环 所以不算内海
memset(d, '0', sizeof d);
memset(st, 0, sizeof st);
getchar();
for (int i = 1;i <= m;i++) {
for (int j = 1;j <= n;j++) {
char c = getchar();
d[i][j] = c;
}
getchar();
}
dfsForSea(0, 0); // 内海不算海 把外海扫一遍标2
for (int i = 1;i <= m;i++) { // 然后扫岛 4和8向同时扫 如果8向扫到2就说明是外岛
for (int j = 1;j <= n;j++) {
if (d[i][j] == '1' && !st[i][j]) {
bool flag = false;
dfsForIsland(i, j, flag);
if (flag) cnt++; // dfs中扫到2就是外岛
}
}
}
cout << cnt << endl;
}
return 0;
}