Skip to content

11994: 【原1994】二哥的地图

题目

题目描述

author: qujun 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1994

题目描述

二哥最近拿到了一份世界地图,这个地图是一个\(N \times M\)的矩阵,每个格子代表一块地方,有可能是陆地或者海洋。

这个地图并没有把国家标注出来,在强烈的好奇心的驱使下,二哥想知道这块地图上有最多可能有多少个国家。在这里,我们认为海洋不属于任何一个国家,每一块陆地属于且仅属于一个国家,并且相邻的陆地属于同一个国家。

输入格式

第一行两个整数N和M,表示地图大小。

接下来N行,每行M个整数。表示这个地图,0代表陆地,-1代表海洋。

输出格式

输出一个整数,表示地图上最多可能的国家数。

数据范围

对于全部数据:\(1 \leq n, m \leq 500\)。 对于50%的数据:\(1 \leq n, m \leq 10\)。

样例输入

3 3
0 -1 0
-1 0 -1
0 -1 0

样例输出

5

限制

时间限制:1000ms,内存限制:65536kb

FineArtz's solution

/* 二哥的地图 */
#include <iostream>
#include <cstring>
using namespace std;

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

int a[505][505];
int n, m;

bool check(int x, int y){
    if (x < 1 || x > n || y < 1 || y > m || a[x][y] != 0) return false;
    return true;
}

void floodfill(int x, int y, int cnt){
    a[x][y] = cnt;
    for (int i = 0; i != 4; ++i){
        int nextx = x + dx[i];
        int nexty = y + dy[i];
        if (check(nextx, nexty)){
            floodfill(nextx, nexty, cnt);
        }
    }
}

int main(){
    memset(a, 0, sizeof(a));
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];
    int cnt = 0;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            if (a[i][j] == 0){
                ++cnt;
                floodfill(i, j, cnt);
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

bool map[509][509] = { 0 };
int dx[] = { 0,1,0,-1 },
dy[] = { 1,0,-1,0 };
int n, m;
void dfs(int x, int y) {
    map[x][y] = false;
    for (int i = 0; i < 4; ++i) {
        if (x + dx[i] >= 0 && x + dx[i] < n && y + dy[i] >= 0 && y + dy[i] < m && map[x + dx[i]][y + dy[i]])
            dfs(x + dx[i], y + dy[i]);
    }
}

int main() {
    scanf("%d %d", &n, &m);

    for(int i=0;i<n;++i)
        for (int j = 0; j < m; ++j) {
            int temp;
            scanf("%d", &temp);
            map[i][j] = (bool)(temp + 1);
        }

    int cnt = 0;
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            if (map[i][j]) {
                ++cnt;
                dfs(i, j);
            }

    cout << cnt;

    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 5e2 + 10;

int N = 0, M = 0, worldMap[maxN][maxN] = {0}, ans = 0;

void DFS(int x, int y);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    for (int i = 0; i < N + 2; i++) {
        for (int j = 0; j < M + 2; j++) {
            if (i == 0 || i == N + 1 || j == 0 || j == N + 1) {
                worldMap[i][j] = 0;
            } else {
                int temp;
                cin >> temp;
                worldMap[i][j] = temp + 1;
            }
        }
    }

    for (int i = 0; i < N + 2; i++) {
        for (int j = 0; j < M + 2; j++) {
            if (worldMap[i][j]) {
                ans++;
                DFS(i, j);
            }
        }
    }

    cout << ans;

    return 0;
}

void DFS(int x, int y) {
    if (!worldMap[x][y]) {
        return;
    } else {
        worldMap[x][y] = 0;
        DFS(x - 1, y);
        DFS(x + 1, y);
        DFS(x, y - 1);
        DFS(x, y + 1);
    }
}

skyzh's solution

#include <iostream>
using namespace std;

int MAP[500][500];
int N, M;
bool visited[500][500] = { 0 };

void visit(int x, int y) {
    static int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
    for (int d = 0; d < 4; d++) {
        int _x = x + dir[d][0];
        int _y = y + dir[d][1];
        if (_x >= 0 && _y >= 0 && _x < N && _y < M) {
            if (!visited[_x][_y] && MAP[_x][_y] == 0) {
                visited[_x][_y] = true;
                visit(_x, _y);
            }
        }
    }
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> MAP[i][j];
        }
    }
    int c = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!visited[i][j] && MAP[i][j] == 0) {
                visit(i, j);
                ++c;
            }
        }
    }
    cout << c << endl;
    return 0;
}

yyong119's solution

#include <cstdio>
#include <cstring>
#include <queue>
#define MAX_N 505
using namespace std;
struct Node {
    int x, y;
    Node(int p = 0, int q = 0): x(p), y(q) {}
};
const int ac[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int n, m, cnt;
int map[MAX_N][MAX_N];
queue<Node> q;
inline int read() {
    char ch = getchar(); int res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res * flag;
}
int main() {
    n = read(), m = read();
    for (register int i = 0; i < n; ++i)
        for (register int j = 0; j < m; ++j)
            map[i][j] = read();
    for (register int i = 0; i < n; ++i)
        for (register int j = 0; j < m; ++j)
            if (!map[i][j]) {
                ++cnt;
                q.push(Node(i, j)); map[i][j] = 1;
                while (!q.empty()) {
                    Node cur = q.front(); q.pop();
                    for (register int k = 0; k < 4; ++k) {
                        int x = cur.x + ac[k][0], y = cur.y + ac[k][1];
                        if (x >= 0 && x < n && y >= 0 && y < m && !map[x][y]) {
                            map[x][y] = 1;
                            q.push(Node(x, y));
                        }
                    }
                }
            }
    printf("%d", cnt);
    return 0;
}

Zsi-r's solution

#include <iostream>

using namespace std;

class DisjointSet{
private:
    int size;
    int *parent;
public:
    DisjointSet(int s);
    ~DisjointSet() { delete[] parent; }
    void Union(int root1, int root2);
    int Find(int x);
    void isOne(int x);
    int countCountry();
    void print();
};

void DisjointSet::print()
{
    for (int i = 0; i < size;i++)
        cout << parent[i] << ' ';
    cout << endl;
}

int DisjointSet::countCountry()
{
    int count = 0;
    for (int i = 0; i < size;i++)
    {
        if (parent[i] < 0)
            count++;
    }
    return count;
}

void DisjointSet::isOne(int x)
{
    parent[x] = 0;
}

DisjointSet::DisjointSet(int s)
{
    size = s;
    parent = new int[size];
    for (int i = 0; i < size;i++)
        parent[i] = -1;
}

int DisjointSet::Find(int x)
{
    if (parent[x]<0)
        return x;
    return parent[x] = Find(parent[x]);
}

void DisjointSet::Union(int root1,int root2)
{
    if (root1==root2)
        return;
    if (parent[root1]>parent[root2])
    {
        parent[root2] += parent[root1];
        parent[root1] = root2;
    }
    else
    {
        parent[root1] += parent[root2];
        parent[root2] = root1;
    }
}

int main()
{
    int m, n;
    cin >> n >> m;
    int **array = new int *[n];
    for (int i = 0; i < n;i++)
    {
        array[i] = new int[m];
        for (int j = 0; j < m;j++)
        {
            cin >> array[i][j];
        }
    }

    //输入的第一行
    DisjointSet djs(n * m);
    if(array[0][0]==-1)
        djs.isOne(0);

    for (int i = 1; i < m; i++)
    {
        if (array[0][i] == -1)
            djs.isOne(i);
        else
            if (array[0][i-1]==0)
                djs.Union(djs.Find(i), djs.Find(i - 1));        
    }


    //接下来的n-1
    for (int i = 1; i < n; i++)
    {
        if (array[i][0]==-1)
            djs.isOne(i* m);
        else 
            if (array[i-1][0]==0)
            djs.Union(djs.Find((i - 1) * m), djs.Find(i * m));
    }


    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j < m; j++)
        {
            if (array[i][j]==-1)
                djs.isOne(i * m + j);
            else 
            {
                if (array[i][j-1]==0)
                    djs.Union(djs.Find(i * m + j - 1), djs.Find(i * m + j));
                if (array[i-1][j]==0)
                    djs.Union(djs.Find(i * m - m + j), djs.Find(i * m + j));
            }
        }
    }

    cout << djs.countCountry() << endl;
    return 0;
}