PP4903 库克船长的宝藏（入门）

解题思路

第一步，理解题意。 沼泽地里绿石头（.）可以走，蓝石头（#）不能走，@ 是起点（也是绿石头）。从起点出发，向上下左右四个方向扩展，数一数能走到多少块绿石头。

第二步，选择算法。 这是经典的"洪水填充"问题，用深度优先搜索（DFS）或广度优先搜索（BFS）都可以。这里用 DFS，写起来最简洁。

第三步，写搜索。 从起点 dfs(sx,sy) 开始，每走到一块绿石头就把计数 cnt 加一，并把它改成 #，防止重复走。然后尝试四个方向，只要没出界且不是蓝石头就继续递归。

第四步，处理多组数据。 题目说有多组测试，遇到 0 0 就结束。每组都要重新计数并输出一行结果。

边界情况。 起点 @ 本身就是一块绿石头，要算进去，所以 cnt 从 1 开始累加（把起点也算进去）。地图最大 20×20，递归深度很小，不用担心栈溢出。

参考代码

// P4903 库克船长的宝藏 深搜：统计能走到的绿色石头数
#include <iostream>
using namespace std;
char mp[25][25]; // 沼泽地图
int w, h, cnt; // w 列, h 行, cnt 可走到的绿石头数
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
void dfs(int x, int y) {
    mp[x][y] = '#'; // 走过后标记为蓝石头，防止重复
    cnt++;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < h && ny >= 0 && ny < w && mp[nx][ny] != '#')
            dfs(nx, ny);
    }
}
int main() {
    int i, j;
    while (cin >> w >> h) {
        if (w == 0 && h == 0) break;
        int sx = 0, sy = 0;
        for (i = 0; i < h; i++) {
            cin >> mp[i]; // 每行 w 个字符
            for (j = 0; j < w; j++)
                if (mp[i][j] == '@') { sx = i; sy = j; } // 起点
        }
        cnt = 0;
        dfs(sx, sy);
        cout << cnt << endl;
    }
    return 0;
}

复杂度分析

时间复杂度是 O(W×H)（每个格子最多被访问一次），空间复杂度也是 O(W×H)。W、H 都不超过 20，非常轻松。