第12课-单元测评(五)

}͆‮

2025-11-14 21:18:01

发布于：浙江

2阅读

0回复

0点赞

T1

给出一个 n×m 的网格，1 表示岛屿，0 表示水域。

网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。计算这个岛屿的周长。

输入格式

第一行两个整数 n,m(1≤n,m≤1000).

接下来 n 行，每行 m 个整数(0 或 1).

输出格式

输出岛屿的周长。

算法分析

可以发现如果一个格子中的一条边是周长的一部分，那么要么它是边界，要么它的两边是 1 和 0。因此可以遍历网格，找到每个陆地的格子，并判断它的四条边哪些是周长的一部分。

参考代码

#include<bits/stdc++.h>
using namespace std;


int a[1009][1009];
int dir[4][2] = { -1,0,0,1,1,0,0,-1 };
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) cin >> a[i][j];
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j]) {
				for (int k = 0; k < 4; k++) {
					int x = i + dir[k][0], y = j + dir[k][1];
					if (x<1 || x>n || y<1 || y>m || !a[x][y]) ans++;
				}
			}
		}
	}
	cout << ans;
	return 0;
}