自动搬运

查看原文

来自洛谷，原作者为

	ZhaoV1 Love

搬运于2025-08-24 22:46:43，当前版本为作者最后更新于2025-04-09 12:08:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目要求求主岛屿个数，即求接触到最外层流入的海水的岛屿个数。直接判断一个岛屿是否是另一个岛屿的子岛屿不好判断，所以不如放弃掉子岛屿，而只关注主岛屿的个数，换句话说，只要接触到从最外层流入的海水的岛屿都一定是主岛屿。

不过，一个主岛屿如果不是通过严格的上下左右操作形成一个环，而是存在类似样例二的斜跨格子的情况，那么该主岛屿并不形成环，换句话说就是海水可以通过斜跨格子的方式流入。

将上述思路运用在代码中就会有以下要点：

1. 海水流入的方向应当有上、下、左、右、左上、右上、左下、右下，八种方向进行操作。
2. 判断岛屿是否是联通，必须严格按照上、下、左、右，四个方向进行连接。
3. 与海水直接接触的岛屿必然是主岛屿。

理解以上要点后，思路就出来了。首先，在地图的最外圈遍历，如果遇到海水 $0$，即需要做八个方向的 bfs 操作。在海水的 bfs 操作中，如果遇到了主岛屿 $1$，则直接对该点进行四个方向的 bfs 操作，并记录答案。

需要注意的是，如果是从所给地图的最外圈进行遍历判断，则需要注意最外圈全部被主岛屿 $1$ 占满的情况，此时答案应特判为 $1$。若是从地图最外圈的更外一圈，也就是虚构的海水进行 bfs 操作，则无需担心该特判问题。（本题解代码用的是前者方式）

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 55;
int t,n,m,res;
bool vis[N][N];
char mp[N][N];
int nextStep[8][2] = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
struct inner{
	int x,y;
};

void bfs1(int x,int y){
	queue<inner> que;
	que.push({x,y});
	res++;

	while(!que.empty()){
		auto tt = que.front();
		que.pop();

		for(int i=0;i<4;i++){
			int tx = tt.x + nextStep[i][0];
			int ty = tt.y + nextStep[i][1];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&mp[tx][ty]=='1'&&!vis[tx][ty]){
				que.push({tx,ty});
				vis[tx][ty] = true;
			}
		}
	}
}

void bfs0(int x,int y){
	queue<inner> que;
	que.push({x,y});
	vis[x][y] = true;

	while(!que.empty()){
		auto tt = que.front();
		que.pop();

		for(int i=0;i<8;i++){
			int tx = tt.x + nextStep[i][0];
			int ty = tt.y + nextStep[i][1];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&!vis[tx][ty]){
				vis[tx][ty] = true;
				if(mp[tx][ty]=='1') bfs1(tx,ty);
				else que.push({tx,ty});
			}
		}
	}
}

void solve(){
	bool flag = false;
	res = 0;
	cin >> n >> m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin >> mp[i][j];
			vis[i][j] = false;
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(i==1 || i==n || j==1 || j==m)//对边缘的海水进行 bfs0
				if(!vis[i][j] && mp[i][j] == '0'){
					bfs0(i,j);
					flag = true;
				}
	if(!flag) res = 1;//以防一个岛屿占满了外边界的情况
	cout << res << '\n';
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> t;
	while(t--){
		solve();
	}
	return 0;
}