solution
数1的块数题,加了内岛不计入的小限制,以及输入数据间没有空格,不是矩阵形式的整数输入。
- 判断是否是子岛屿:如果该岛屿有边缘部分或者可以通过外海走到边缘部分说明不是子岛屿
#include<iostream>
#include<queue>
#include<string>
using namespace std;
const int maxn = 55;
int t, n, m, a[maxn][maxn], flag[maxn][maxn], vis[maxn][maxn], ans;
string s;
struct Node{int x, y;
}node, node1;
int X[8] = {-1, 1, 0, 0, 1, -1, 1, -1};
int Y[8] = {0, 0, -1, 1, 1, -1, -1, 1};void bfs(int x, int y){queue<Node> q;node.x = x;node.y = y;flag[x][y] = 1;q.push(node);while(!q.empty()){Node top = q.front();q.pop();for(int i = 0; i < 4; i++){int newx = top.x + X[i];int newy = top.y + Y[i];if(newx < 0 || newx >= m || newy < 0 || newy >= n) continue;if(flag[newx][newy] || !a[newx][newy]) continue;node1.x = newx;node1.y = newy;flag[newx][newy] = 1;q.push(node1);}}
}bool judge(int x, int y){for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){vis[i][j] = 0;}}queue<Node> q;node.x = x;node.y = y;vis[x][y] = 1;q.push(node);while(!q.empty()){Node top = q.front();q.pop();if(top.x == 0 || top.x == m - 1 || top.y == 0 || top.y == n - 1) return true;//能走到边缘就证明没有在环内for(int i = 0; i < 8; i++){int newx = top.x + X[i];int newy = top.y + Y[i];if(vis[newx][newy] || a[newx][newy]) continue;if(x < 0 || x >= m || y < 0 || y >= n) continue;node1.x = newx;node1.y = newy;q.push(node1);vis[newx][newy] = 1;}}return false;
}int main(){scanf("%d", &t);while(t--){scanf("%d%d", &m, &n);ans = 0;for(int i = 0; i < m; i++){cin >> s;for(int j = 0; j < n; j++){a[i][j] = s[j] - '0';flag[i][j] = 0;}}for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(!flag[i][j] && a[i][j]){bfs(i, j);if(judge(i, j)) ans ++;}}}printf("%d\n", ans);} return 0;
}