P4914 能养几只公羊（基础）

解题思路

第一步，理解题意。 农场是一个n行m列的方格，0表示空地，1表示墙。公羊会在空地上上下左右走动，但不能穿墙。两只公羊不能见面，也就是不能待在同一个连通的空地区域里，否则它们走着走着就会碰见。问最多能养几只公羊。

第二步，转化成连通块问题。 两块空地如果在上下左右四个方向上能通过空地连在一起，它们就在同一个连通块里。一个连通块里只能放1只公羊，因为两只公羊同在一个连通块里总有一天会碰面。所以答案就是空地的连通块个数。

第三步，用广度优先搜索数连通块。 用数组g记录每个格子是0还是1，用两个大数组qx、qy当作队列。依次扫描每个格子，遇到没被访问过的空地（值是0）就把答案加1，然后从这个格子出发做BFS：把它上下左右四个方向上的空地全部改成墙（标记成1），表示这个连通块已经被数过了。

第四步，注意范围。 n和m最大都是1000，格子总数最多100万，队列数组要开到100万以上。输入每个格子是一个字符0或1，用cin直接读字符即可。判断新位置时要注意不能超出农场的边界。

第五步，验证例子。 题目给的4×5农场，空地被墙分成3个连通块：左上一片连通的空地、中间单独一块、右下一大片，所以答案是3。如果整个农场全是墙，没有空地，答案就是0。

参考代码

// 能养几只公羊：求空地0的连通块个数，每个连通块最多放1只公羊
#include <iostream>
using namespace std;
char g[1005][1005];
int qx[1000005], qy[1000005];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> g[i][j];
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (g[i][j] == '0') {
                ans++;
                // 广度优先搜索，把这个连通块全部改成墙
                int head = 0, tail = 0;
                qx[tail] = i; qy[tail] = j; tail++;
                g[i][j] = '1';
                while (head < tail) {
                    int x = qx[head], y = qy[head];
                    head++;
                    for (int d = 0; d < 4; d++) {
                        int nx = x + dx[d], ny = y + dy[d];
                        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] == '0') {
                            g[nx][ny] = '1';
                            qx[tail] = nx; qy[tail] = ny; tail++;
                        }
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

每个格子最多被访问一次，每次访问做常数次操作，所以时间复杂度是O(n·m)。n、m最大1000，100万个格子，运行非常快。空间上需要存g数组和两个队列数组，各约100万，空间复杂度O(n·m)。