【题解】红与黑

题目链接：红与黑

DFS 关键点

1. 在 dfs 问题中， st 标记数组是不可缺少的。st 数组的用法取决于所处理的 dfs 问题属于哪种模型。例如：如果是基于连通性的模型，由于我们在棋盘的内部进行搜索，每个点视为一个状态，遍历的是所有点的集合，所以需要用 st 数组标记遍历到的点，并且不再取消标记，防止重复遍历到同一点；如果是其它 DFS 问题，我们将整个棋盘所有点的集合视为一个状态，搜索当前状态能否转移到目标状态，在搜索当前状态的一个分支前需要先将当前状态标记，搜索完该分支后，需要将当前状态标记取消再搜索当前状态的下一个分支。st 标记的取消与否影响到我们是否可以回溯。
2. 是否需要恢复现场本质上取决我们搜索下一个状态时，当前状态是否相同 。如果当前状态相同，就不用恢复现场。例如从棋盘上的某个点走到相邻点，无论走哪个相邻点，当前点都必须走到，所以不用恢复现场。如果当前状态不同，就需要恢复现场。例如搜索棋盘染色的不同状态时，起始状态棋盘是没有染过色的，我们搜索完将第一个格子染色的分支后，就需要先将第一个格子的标记取消，再搜索第一个格子不染色第二个格子染色的分支。

法一：dfs 32ms

c++

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <unordered_map>
#include <map>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second


const int N = 20 + 10;

string g[N];
int r, c, ans;
int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
bool st[N][N];

int dfs(int x, int y)
{
    //if (g[x][y] == '#') return 0;

    int sum = 1;
    for (int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= r || b < 0 || b >= c) continue;
        if (st[a][b] || g[a][b] == '#') continue;
        st[a][b] = true;
        sum += dfs(a, b);
    }

    return sum;
}

int main()
{
    while (scanf("%d%d", &c, &r), r && c)
    {
        for (int i = 0; i < r; i ++ ) cin >> g[i];

        for (int i = 0; i < r; i ++ )
        {
            for (int j = 0; j < c; j ++ )
            {
                if (g[i][j] == '@')
                {
                    st[i][j] = true;
                    cout << dfs(i, j) << endl;
                    break;
                }
            }
        }
        memset(st, false, sizeof st);
    }

    return 0;
}

法二：bfs 51ms

c++

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <unordered_map>
#include <map>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second


const int N = 20 + 10;

string g[N];
int r, c, ans;
int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
bool st[N][N];

int bfs(int sx, int sy)
{
    memset(st, false, sizeof st);
    queue<PII> q;
    q.push({sx, sy});
    st[sx][sy] = true;

    int sum = 1;
    while (q.size())
    {
        int x = q.front().x, y = q.front().y;
        q.pop();

        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < r && b >= 0 && b < c && g[a][b] != '#' && !st[a][b])
            {
                sum ++ ;
                q.push({a, b});
                st[a][b] = true;
            }
        }
    }

    return sum;
}

int main()
{
    while (scanf("%d%d", &c, &r), r && c)
    {
        for (int i = 0; i < r; i ++ ) cin >> g[i];

        for (int i = 0; i < r; i ++ )
        {
            for (int j = 0; j < c; j ++ )
            {
                if (g[i][j] == '@')
                {
                    cout << bfs(i, j) << endl;
                    break;
                }
            }
        }
    }

    return 0;
}