题解 | #点燃星海#

H. 点燃星海

知识点：深搜/广搜/并查集

实际上就是计算连通块的数量。

搜索入门题，没什么要讲的地方。

也可以用并查集进行合并，不用搜索。

标程

C++

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 1000 + 9;
constexpr int path[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int n, m;
char a[N][N];

void dfs(int x, int y)
{
    a[x][y] = '0';
    for (auto [dx, dy] : path)
    {
        int nx = (x + dx + n) % n;
        int ny = (y + dy + m) % m;
        if (a[nx][ny] == '1')
        {
            dfs(nx, ny);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }

    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (a[i][j] == '1')
            {
                ++ans;
                dfs(i, j);
            }
        }
    }
    cout << ans << '\n';
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static Kattio io = new Kattio();

    final static int N = 1000 + 9;
    static int n, m;
    static char[][] a = new char[N][];
    final static int path[][] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    static void bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y});
        a[x][y] = '0';
        while (!q.isEmpty()) {
            int[] p = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = (p[0] + path[i][0] + n) % n;
                int ny = (p[1] + path[i][1] + m) % m;
                if (a[nx][ny] == '1') {
                    a[nx][ny] = '0';
                    q.add(new int[]{nx, ny});
                }
            }
        }
    }

    public static void main(String[] args) {
        n = io.nextInt();
        m = io.nextInt();
        for (int i = 0; i < n; i++) {
            a[i] = io.next().toCharArray();
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] == '1') {
                    ans++;
                    bfs(i, j);
                }
            }
        }
        io.println(ans);

        io.close();
    }
}

class Kattio extends PrintWriter {
    private BufferedReader r;
    private StringTokenizer st;
    // 标准 IO
    public Kattio() { this(System.in, System.out); }
    public Kattio(InputStream i, OutputStream o) {
        super(o);
        r = new BufferedReader(new InputStreamReader(i));
    }
    // 在没有其他输入时返回 null
    public String next() {
        try {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(r.readLine());
            return st.nextToken();
        } catch (Exception e) {}
        return null;
    }
    public int nextInt() { return Integer.parseInt(next()); }
    public double nextDouble() { return Double.parseDouble(next()); }
    public long nextLong() { return Long.parseLong(next()); }
}

Python

from collections import deque

dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]

n, m = map(int, input().split())
a = []
for i in range(n):
    a.append(list(map(int, input())))


def bfs(x, y):
    q = deque([(x, y)])
    a[x][y] = 0
    while q:
        x, y = q.popleft()
        for dx, dy in dirs:
            nx = (x + dx + n) % n
            ny = (y + dy + m) % m
            if a[nx][ny] == 1:
                a[nx][ny] = 0
                q.append((nx, ny))


ans = 0
for i in range(n):
    for j in range(m):
        if a[i][j] == 1:
            ans += 1
            bfs(i, j)
print(ans)