信息学奥赛一本通 1359：围成面积

【题目链接】

ybt 1359：围成面积

【题目考点】

1. 搜索：连通块问题

【解题思路】

解法1：遍历外圈

遍历整个地图的外圈（第1行、第1列、第10行，第10列），从外圈所有标记为0的位置开始搜索，把搜索到的位置标记为2。
此时所有值为2的位置都是图形外面的位置，值为1的位置是图形的边线，值为0的位置为图形内。统计值为0的位置是数量，即为该图形的面积。

解法2：构造外圈连通块

由于图形的边线就可以在整个地图的外圈，为了让整个图形外面的区域构成一个完整的连通块，我们可以人为扩大地图边界。原来地图的行、列是1到10。现在扩展出第0行、第0列、第11行、第11列，这几行几列的标记都为0。扩展后的行列与原图形外面的位置会形成一个完整的连通块。此时只需要从(0,0)位置开始一次搜索，就可以将整个连通块中每个位置都标记为2。后面还是统计值为0的位置的数量。

本题可以用深搜或广搜来解决。

【题解代码】

解法1：遍历外圈

• 深搜

#include<bits/stdc++.h>
using namespace std;
#define N 15
int n, a[N][N], ans;//a[i][j]:(i,j)位置标记的数字 
int dir[4][2] = {
    {
    0, 1}, {
    0, -1}, {
    1, 0}, {
    -1, 0}};
void dfs(int sx, int sy)
{
    
	for(int i = 0; i < 4; ++i)
	{
    
		int x = sx + dir[i][0], y = sy + dir[i][1];
		if(x >= 1 && x <= n && y >= 1 && y <= n && a[x][y] == 0)
		{
     
			a[x][y] = 2;
			dfs(x, y);
		}
	}
}
int main()
{
    
    n = 10;//地图范围：行列1~n 
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			cin >> a[i][j];
	for(int i = 1; i <= n; ++i)//遍历外圈 
    {
    
        if(a[1][i] == 0)
        {
    
            a[1][i] = 2;
            dfs(1, i);
        }
        if(a[n][i] == 0)
        {
    
            a[n][i] = 2;
            dfs(n, i);
        }
        if(a[i][1] == 0)
        {
    
            a[i][1] = 2;
            dfs(i, 1);
        }
        if(a[i][n] == 0)
        {
    
            a[i][n] = 2;
            dfs(i, n);
        }
    }
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
		{
    
			if(a[i][j] == 0)
			    ans++;//面积加1 
		}
	cout << ans;
	return 0;
}

• 广搜

#include<bits/stdc++.h>
using namespace std;
#define N 15
struct Node
{
    
    int x, y;
    Node(){
    }
    Node(int a, int b):x(a), y(b){
    }
};
int n, a[N][N], ans;//a[i][j]:(i,j)位置标记的数字 
int dir[4][2] = {
    {
    0, 1}, {
    0, -1}, {
    1, 0}, {
    -1, 0}};
void bfs(int sx, int sy)
{
    
    queue<Node> que;
    a[sx][sy] = 2;
    que.push(Node(sx, sy));
    while(que.empty() == false)
    {
    
        Node u = que.front();
        que.pop();
        for(int i = 0; i < 4; ++i)
        {
    
            int x = u.x + dir[i][0], y = u.y + dir[i][1];
            if(x >= 1 && x <= n && y >= 1 && y <= n && a[x][y] == 0)
            {
    
                a[x][y] = 2;
                que.push(Node(x, y));
            }    
        }
    }
}
int main()
{
    
    n = 10;//地图范围：行列1~n 
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			cin >> a[i][j];
	for(int i = 1; i <= n; ++i)//遍历外圈 
    {
    
        if(a[1][i] == 0)
            bfs(1, i);
        if(a[n][i] == 0)
            bfs(n, i);
        if(a[i][1] == 0)
            bfs(i, 1);
        if(a[i][n] == 0)
            bfs(i, n);
    }
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
		{
    
			if(a[i][j] == 0)
			    ans++;//面积加1 
		}
	cout << ans;
	return 0;
}

解法2：构造外圈连通块

• 深搜

#include<bits/stdc++.h>
using namespace std;
#define N 15
int n, a[N][N], ans;//a[i][j]:(i,j)位置标记的数字 
int dir[4][2] = {
    {
    0, 1}, {
    0, -1}, {
    1, 0}, {
    -1, 0}};
void dfs(int sx, int sy)
{
    
	for(int i = 0; i < 4; ++i)
	{
    
		int x = sx + dir[i][0], y = sy + dir[i][1];
		if(x >= 0 && x <= n+1 && y >= 0 && y <= n+1 && a[x][y] == 0)//地图范围：0~n+1 
		{
     
			a[x][y] = 2;
			dfs(x, y);
		}
	}
}
int main()
{
    
    n = 10;//扩展边界后，地图范围：行列 0~n+1 
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			cin >> a[i][j];
	a[0][0] = 2;
	dfs(0, 0);
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
		{
    
			if(a[i][j] == 0)
			    ans++;//面积加1 
		}
	cout << ans;
	return 0;
}

• 广搜

#include<bits/stdc++.h>
using namespace std;
#define N 15
struct Node
{
    
    int x, y;
    Node(){
    }
    Node(int a, int b):x(a), y(b){
    }
};
int n, a[N][N], ans;//a[i][j]:(i,j)位置标记的数字 
int dir[4][2] = {
    {
    0, 1}, {
    0, -1}, {
    1, 0}, {
    -1, 0}};
void bfs(int sx, int sy)
{
    
    queue<Node> que;
    a[sx][sy] = 2;
    que.push(Node(sx, sy));
    while(que.empty() == false)
    {
    
        Node u = que.front();
        que.pop();
        for(int i = 0; i < 4; ++i)
        {
    
            int x = u.x + dir[i][0], y = u.y + dir[i][1];
            if(x >= 0 && x <= n+1 && y >= 0 && y <= n+1 && a[x][y] == 0)//地图范围为0~n+1
            {
    
                a[x][y] = 2;
                que.push(Node(x, y));
            }
        }
    }
}
int main()
{
    
    n = 10;//扩展边界后，地图范围：行列 0~n+1 
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			cin >> a[i][j];
	bfs(0, 0);
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
		{
    
			if(a[i][j] == 0)
			    ans++;//面积加1 
		}
	cout << ans;
	return 0;
}