搜索，问题 I: 围成面积

题目描述

编程计算由“*”号围成的下列图形的面积。面积计算方法是统计*号所围成的闭合曲线中水平线和垂直线交点的数目。如下图所示，在10×10的二维数组中，有“*”围住了15个点，因此面积为15。

输入

10×10的图形。

输出

输出面积。

样例输入 复制

0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0

样例输出 复制

15

题解

 使用淹没小岛的思想，中间要求取的面积是淹没不到的部分（陆地），其余部分均可被淹没（水域），在地面和水域之间由1来隔开，那么从外往里进行淹没，遇到1跳过（被1隔开淹没不进去），遇到0淹没（将值设为-1）。淹没过程结束后，地图上只有-1（水域），1（分割线），0（陆地），统计0的个数即可。

代码

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

int mp[15][15];

int ans;
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

void dfs(int x, int y){
	if(mp[x][y] == -1 ||mp[x][y] == 1)return ;
	mp[x][y] = -1;
	for(int k = 0;k < 4;k ++){
		int nx = x + dx[k],ny = y + dy[k];
		if(nx < 0 || ny < 0 || nx > 11 || ny > 11)continue;
		dfs(nx, ny);
	}
}

int main(){
	for(int i = 1;i <= 10;i ++)
		for(int j = 1;j <= 10;j ++)cin >> mp[i][j];
	dfs(1, 1);
//	for(int i = 1;i <= 10;i ++){
//		for(int j = 1;j <= 10;j ++)
//		cout << mp[i][j] << ' ';
//		cout << '\n';
//	}

	for(int i = 1;i <= 10;i ++)
		for(int j = 1;j <= 10;j ++)
			if(mp[i][j] == 0)ans ++;
	cout << ans << '\n';
	return 0;
}