算法1
C++ 代码
#include <bits/stdc++.h>
using namespace std;
//统计可以到达地图边界的岛屿的数量,最外侧的岛屿一定是外岛屿,因为没有其他岛屿可以再包围它
int t, m, n, res;
#define x first
#define y second
int mp[55][55];
bool st[55][55], se[55][55], tag;
typedef pair<int,int> pii;
//DLRU简单来个字典序
int dx[4] = {1,0,0,-1};
int dy[4] = {0,-1,1,0};
int dxx[8] = {1,0,0,-1,1,-1,1,-1};
int dyy[8] = {0,-1,1,0,-1,1,1,-1};
bool inmap(int xx, int yy){
return xx >= 1 && xx <= m && yy >= 1 && yy <= n;
}
void bfs(int a, int b){
if(a == 1 || a == m || b == 1 || b == n) tag = true;
queue<pii> q; q.push({a,b}); st[a][b] = true; //存坐标
while(q.size()){
auto p = q.front(); q.pop();
if(p.x == 1 || p.x == m || p.y == 1 || p.y == n) tag = true;
//int xx = p.x, yy = p.y;
for(int i = 0; i < 4; ++ i){
int xx = p.x + dx[i], yy = p.y + dy[i];
if(inmap(xx,yy) && !st[xx][yy] && mp[xx][yy]){
q.push({xx,yy});
st[xx][yy] = true;
}
}
}
}
void bfs2(int a, int b){
memset(se, false, sizeof(se));
queue<pii> q; q.push({a,b}); se[a][b] = true;
while(q.size()){
auto p = q.front(); q.pop();
//枚举周围海域的时候就逐个判断是否已经到达了边界,是则直接return,答案加1
if(p.x == 1 || p.x == m || p.y == 1 || p.y == n) {
res ++; return ;
}
for(int i = 0; i < 8; ++ i){
int xx = p.x + dxx[i], yy = p.y + dyy[i];///!!!!!!!注意审题和样例细节
if(inmap(xx,yy) && !se[xx][yy] && !mp[xx][yy]){//题目已经给出了水域是八连通的,岛屿题目给出四连通
q.push({xx,yy});
se[xx][yy] = true;
}
}
}
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> t;
while(t --){
memset(mp, 0, sizeof(mp)); res = 0;
memset(st, 0, sizeof(st));
memset(se, false, sizeof(se));
cin >> m >> n;
string s[55];
for(int i = 1; i <= m; ++ i) cin >> s[i];
for(int i = 1; i <= m; ++ i)
for(int j = 1; j <= n; ++ j) mp[i][j] = s[i][j - 1] - '0';
// for(int i = 1; i <= m; ++ i){
// for(int j = 1; j <= n; ++ j) cout << mp[i][j];
// cout << '\n';
// }
//从开头逐个扫描陆地,然后单独处理并记录它,然后再扫描其它没有记录过的陆地
for(int i = 1; i <= m; ++ i){
for(int j = 1; j <= n; ++ j){
if(mp[i][j] && !st[i][j]) {///是陆地,且没有访问过的情况下
//tag = false;
bfs(i,j);
if(tag){
res ++; tag = false; continue;
}
bfs2(i,j);
}
}
}
cout << res << '\n';
}
return 0;
}