站外题求助

奶牛 Bessie 正准备从她最喜爱的草地回到她的牛棚。农场位于一个 N×N 的方阵上（2≤N≤50），其中她的草地在左上角，牛棚在右下角。Bessie 想要尽快回家，所以她只会向下或向右走。有些地方有草堆（haybale），Bessie 无法穿过；她必须绕过它们。 Bessie 今天感到有些疲倦，所以她希望改变她的行走方向至多 K 次（1≤K≤3）。 Bessie 有多少条不同的从她最爱的草地回到牛棚的路线？如果一条路线中 Bessie 经过了某个方格而另一条路线中没有，则认为这两条路线不同。

输入格式

每个测试用例的输入包含 T 个子测试用例，每个子测试用例描述了一个不同的农场，并且必须全部回答正确才能通过整个测试用例。输入的第一行包含 T（1≤T≤50）。每一个子测试用例如下。每个子测试用例的第一行包含 N 和 K。以下 N 行每行包含一个长为 N 的字符串。每个字符为 .，如果这一格是空的，或 H，如果这一格中有草堆。输入保证农场的左上角和右下角没有草堆。

CPP

#include <bits/stdc++.h>
using namespace std;
char m[55][55], sum = 0;
void dfs(int k, int i, int j, int n, int f)
{
    if (i == n && j == n)
    {
        sum++;
        return;
    }
    if (i > n || j > n)
    {
        return;
    }
    if (k > 0)
    {
        if (f == 0)
        {
            int xx = i + 1;
            int yy = j;
            if (m[xx][yy] != 'H')
                dfs(k - 1, xx, yy, n, 1);
        }
        else
        {
            int xx = i;
            int yy = j + 1;
            if (m[xx][yy] != 'H')
                dfs(k - 1, xx, yy, n, 0);
        }
    }
    if (f == 0)
    {
        if (m[i][j + 1] != 'H')
        {
            return dfs(k, i, j + 1, n, 0);
        }
        else
            return;
    }
    else
    {
        if (m[i + 1][j] != 'H')
        {

            return dfs(k, i + 1, j, n, 1);
        }
        else
            return;
    }
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n >> k;
        for (int i = 0; i <= n + 1; i++)
            m[i][0] = 'H';
        for (int j = 0; j <= n + 1; j++)
            m[0][j] = 'H';
        sum = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
                cin >> m[i][j];
        }
        dfs(k, 0, 0, n, 0);
        dfs(k, 0, 0, n, 1);
        cout << sum << endl;
    }
    return 0;
}

为啥我的代码没输出

讨论操作

回复

相关推荐

站外题求助