• Uncategorized
  • 0

[C++] Identify the lake (queue + Pair)

Hits: 0

Help freshman AC with a question

Problem Description A
[grid] map consists of a grid of n rows and n columns, and each grid is initially filled with zeros. Geological surveyors use the number 1 on the grid map to enclose the only lake boundary in a circle, and the circle can only follow four directions of up, down, left and right. The lake is the area enclosed by the number 1 (excluding 1). Please write a program to fill the area of ​​the lake with the number 2.

Input form
Input an integer n (0<n<=30) in the first line;
each of the following n lines consists of 0 or 1 separated by spaces.

Output form
Output n rows and n columns, and mark the area of ​​the lake with 2.

Example 1 Input
6
0 0 0 0 0 0
0 1 1 1 1 1
0 1 0 0 0 1
0 1 0 0 1 1
0 1 1 0 1 0
0 0 1 1 1 0
Example 1 Output
0 0 0 0 0 0
0 1 1 1 1 1
0 1 2 2 2 1
0 1 2 2 1 1
0 1 1 2 1 0
0 0 1 1 1 0

Example 2 Input
4
0 1 1 1
1 1 0 1
1 0 0 1
1 1 1 1
Example 2 Output
0 1 1 1
1 1 2 1
1 2 2 1
1 1 1 1

Example 3 Input
4
1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1
Example 3 Output
1 1 1 1
1 2 2 1
1 2 2 1
1 1 1 1

The same type of topic “Island Problem” has appeared on leetcode. This kind of topic is mainly solved through search algorithms (deep search dfs or wide search bfs). The more difficult ones need to be pruned to pass. Here we mainly use the queue. Data structure + pair technology to achieve.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

int dir[ 4 ][ 2 ] = { -1 , 0 , 1 , 0 , 0 , -1 , 0 , 1 };
int a[ 40 ][ 40 ], vis[ 40 ][ 40 ];

int main()
{
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);

    queue<PII> qu;
    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= n + 1; j++)
            if (i == 0 || i == n + 1 || j == 0 || j == n + 1)
            {
                qu.push(make_pair(i, j)), vis[i][j] = 1;
            }

    while (!qu.empty())
    {
        PII p = qu.front(); qu.pop();
        int x = p.first, y = p.second;
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dir[i][ 0 ], ny = y + dir[i][ 1 ];
            if (nx < 0 || nx > n + 1 || ny < 0 || ny > n + 1 || a[nx][ny] || vis[nx][ny]) continue ;
            qu.push(make_pair(nx, ny)), vis[nx][ny] = 1;
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (a[i][j] == 0 && vis[i][j] == 0) a[i][j] = 2;
            if (j > 1) printf(" ");
            printf("%d", a[i][j]);
        }
        printf("\n");
    }

    return 0;
}

You may also like...

Leave a Reply

Your email address will not be published.