题目传送门

史：

#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++)
        {
            for (int j = 0; j <= n + 1; j++)
            {
                m[i][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;
}