题面：

测试点 #$\tt{1}$：

in

7
3 1
...
...
...
3 2
...
...
...
3 3
...
...
...
3 3
...
.H.
...
3 2
.HH
HHH
HH.
3 3
.H.
H..
...
4 3
...H
.H..
....
H...

out

2
4
6
2
0
0
6

老师给的题解：

题解代码（虽然代码，貌似并不相干）：

#include <iostream>
#include <string>
#include <vector>

using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<string> g(n);
    for (int i = 0; i < n; i++) cin >> g[i];
    int ret = 0;
    if (k >= 1) {
        bool urcorner = true;
        bool dlcorner = true;
        for (int i = 0; i < n; i++) {
            if (g[0][i] == 'H' || g[i][n - 1] == 'H') urcorner = false;
            if (g[i][0] == 'H' || g[n - 1][i] == 'H') dlcorner = false;
        }
        ret += urcorner;
        ret += dlcorner;
    }
    if (k >= 2) {
        // use column j
        for (int j = 1; j < n - 1; j++) {
            bool valid = true;
            for (int i = 0; i < n; i++) {
                if (g[i][j] == 'H') valid = false;
                if (i < j && g[0][i] == 'H') valid = false;
                if (i > j && g[n - 1][i] == 'H') valid = false;
            }
            ret += valid;
        }
        // use row i
        for (int i = 1; i < n - 1; i++) {
            bool valid = true;
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 'H') valid = false;
                if (j < i && g[j][0] == 'H') valid = false;
                if (j > i && g[j][n - 1] == 'H') valid = false;
            }
            ret += valid;
        }
    }
    if (k >= 3) {
        for (int i = 1; i < n - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                // RDRD
                bool valid = g[i][j] == '.';
                for (int a = 0; a < n; a++) {
                    if (a <= i && g[a][j] == 'H') valid = false;
                    if (a >= i && g[a][n - 1] == 'H') valid = false;
                    if (a <= j && g[0][a] == 'H') valid = false;
                    if (a >= j && g[i][a] == 'H') valid = false;
                }
                ret += valid;
                valid = g[i][j] == '.';
                // DRDR
                for (int a = 0; a < n; a++) {
                    if (a <= i && g[a][0] == 'H') valid = false;
                    if (a >= i && g[a][j] == 'H') valid = false;
                    if (a <= j && g[i][a] == 'H') valid = false;
                    if (a >= j && g[n - 1][a] == 'H') valid = false;
                }
                ret += valid;
            }
        }
    }
    cout << ret << "\n";
}
int main() {
    int t;
    cin >> t;
    while (t--) solve();
}

我：认为用 DP 最简洁（（（

于是我就写了一个 DP（40分（（（就连测试点 #$\tt{1}$ 都没过（

#include <bits/stdc++.h>
using namespace std;
int t, n, m;
char ch[55][55];
bool vis[55][55];
int dp[55][55][10][2];
//   dp[位置i][位置j][使用的机会次数][向下/向右];
vector<int> ans;   
int main() {
//  freopen("turn.in", "r", stdin);
//  freopen("turn.out", "w", stdout);
  cin >> t;
  while (t--) {
    memset(dp, 0, sizeof(dp));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= n; j++) {
    		cin >> ch[i][j];
		}
	}
	dp[1][1][0][0] = 1;
	dp[1][1][0][1] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 0; k <= m; k++) {
				if (ch[i][j] == 'H') {
					dp[i][j][k][0] = 0;
					dp[i][j][k][1] = 0;
					continue;
				}
				if (i == 1 && j == 1) {
					continue;
				}
				dp[i][j][k][0] = dp[i][j - 1][k - 1][1] + dp[i - 1][j][k][0];
				dp[i][j][k][1] = dp[i][j - 1][k][1] + dp[i - 1][j][k - 1][0];
			}
		}
	}
	int sum = 0;
	/*
	for (int k = 1; k <= m; k++) {
	//cout << dp[n][n][1][0] << "\n";
		cout << dp[n][n][k][0] << "\n";
		cout << dp[n][n][k][1] << "\n";
		sum = sum + dp[n][n][k][0] + dp[n][n][k][1];
	}
	*/
	sum = sum + dp[n][n][m][0] + dp[n][n][m][1];
	ans.push_back(sum);
  }
  for (int i = 0; i < ans.size(); i++) {
	cout << ans[i] << "\n";
  }
  return 0;
}

求调（（（悬赏关注（（（