【题解】P7995 [USACO21DEC] Walking Home B

ZBAA_MKC · 2021-12-26 12:33:40 · 题解

~~我为啥感觉T3最简单T1最难~~

没看出来怎么用dp，我是用搜索写的。

这题搜索部分和走迷宫的题目大部分是相同的，唯一需要特殊处理的变向次数。就是在走下一步需要变向时判一下之前的次数，如果次数已经满了就不拐弯。

开始的时候我们搜两次，一次从起点往右搜，另一个往下搜。

代码如下

#include <bits/stdc++.h>
using namespace std;
int n, k;
char c[55][55];
int ans = 0;
const int dx[2] = {1, 0};
const int dy[2] = {0, 1};

void dfs(int x, int y, int cnt, int now)
{
    if (x > n || y > n || c[x][y] == 'H' || cnt > k)
    {
        return;
    }
    if (x == n && y == n)
    {
        ans++;
        return;
    }
    for (register int i = 0; i < 2; i++)
    {
        if (now == i)
        {
            dfs(x + dx[i], y + dy[i], cnt, i);
        }
        else
        {
            if (cnt != k)
            {
                dfs(x + dx[i], y + dy[i], cnt + 1, i);
            }
        }
    }

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> k;
        ans = 0;
        for (register int i = 1; i <= n; i++)
        {
            for (register int j = 1; j <= n; j++)
            {
                cin >> c[i][j];
            }
        }
        dfs(2, 1, 0, 0);
        dfs(1, 2, 0, 1);
        cout << ans << endl;
    }
    return 0;
}