Informatics Olympiad all in one 1359: enclosed area

【 Topic link 】

ybt 1359： Enclosed area

【 Topic test site 】

1. Search for ： Connected block problem

【 Their thinking 】

solution 1： Traverse outer circle

Traverse the outer circle of the entire map （ The first 1 That's ok 、 The first 1 Column 、 The first 10 That's ok , The first 10 Column ）, All marks from the outer ring are 0 The location starts to search , Mark the searched location as 2.
At this point, all values are 2 The positions of are all outside the figure , The value is 1 The position of is the edge of the figure , The value is 0 The position of is in the graph . The statistical value is 0 The position of is quantity , Is the area of the figure .

solution 2： Construct outer ring connected block

Because the edge line of the graph can be in the outer circle of the whole map , In order to make the area outside the whole graph form a complete connected block , We can artificially enlarge the boundaries of the map . The line of the original map 、 The column is 1 To 10. Now expand to the 0 That's ok 、 The first 0 Column 、 The first 11 That's ok 、 The first 11 Column , These rows and columns are marked with 0. The extended row and column will form a complete connected block with the position outside the original graph . At this point, you only need to start from (0,0) Position to start a search , You can mark each position in the entire connected block as 2. Later, the statistical value is 0 The number of locations .

This problem can be solved by deep search or wide search .

【 Solution code 】

solution 1： Traverse outer circle

• Deep search

#include<bits/stdc++.h>
using namespace std;
#define N 15
int n, a[N][N], ans;//a[i][j]:(i,j) The number of position marks  
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;// Map range ： The ranks of 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)// Traverse outer circle  
    {
    
        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++;// Area plus 1 
		}
	cout << ans;
	return 0;
}

• Guang Shu

#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) The number of position marks  
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;// Map range ： The ranks of 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)// Traverse outer circle  
    {
    
        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++;// Area plus 1 
		}
	cout << ans;
	return 0;
}

solution 2： Construct outer ring connected block

• Deep search

#include<bits/stdc++.h>
using namespace std;
#define N 15
int n, a[N][N], ans;//a[i][j]:(i,j) The number of position marks  
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)// Map range ：0~n+1 
		{
     
			a[x][y] = 2;
			dfs(x, y);
		}
	}
}
int main()
{
    
    n = 10;// After expanding the boundary , Map range ： The ranks of  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++;// Area plus 1 
		}
	cout << ans;
	return 0;
}

• Guang Shu

#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) The number of position marks  
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)// The map range is 0~n+1
            {
    
                a[x][y] = 2;
                que.push(Node(x, y));
            }
        }
    }
}
int main()
{
    
    n = 10;// After expanding the boundary , Map range ： The ranks of  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++;// Area plus 1 
		}
	cout << ans;
	return 0;
}