P7995 [USACO21DEC] Walking Home B 题解

幸存者 · 2021-12-24 16:15:41 · 题解

思路

一看到这道题，就想到了 dfs 的做法。

定义一个变量 cnt 计数，直接枚举每一步向哪个方向走，如果都走不了就返回即可。

注意：这里需要使用剪枝，如果已经达到了 k 次，并且不在最后一行或最后一列，直接返回即可。

AC Code

#include <iostream>
using namespace std;
int n, k, cnt = 0;
bool a[60][60];
void dfs(int x, int y, int w, int s)
{
    if (s > k) return;
    if (s == k && x != n && y != n) return;
    if (x == n && y == n)
    {
        cnt++;
        return;
    }
    if (!a[x + 1][y] && !a[x][y + 1]) return;
    if (x == 1 && y == 1)
    {
        if (a[x + 1][y]) dfs(x + 1, y, 1, s);
        if (a[x][y + 1]) dfs(x, y + 1, 0, s);
    }
    else
    {
        if (a[x + 1][y])
        {
            if (w == 1) dfs(x + 1, y, 1, s);
            else dfs(x + 1, y, 1, s + 1);
        }
        if (a[x][y + 1])
        {
            if (w == 0) dfs(x, y + 1, 0, s);
            else dfs(x, y + 1, 0, s + 1);
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        cnt = 0;
        cin >> n >> k;
        for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++)
        {
            char c;
            cin >> c;
            if (c == '.') a[j][k] = 1;
            else a[j][k] = 0;
        }
        dfs(1, 1, 1, 0);
        cout << cnt << endl;
    }
    return 0;
}