一眼秒了是 dp 。

刚开始做用 $dp_{i,j,k}$ 表示走到第 $i$ 行第 $j$ 列，改变方向 $k$ 次，有多少条不同的路线。

手画一下发现要多加一维记录每一步走的方向。

$dp_{i,j,k,0}=dp_{i-1,j,k-1,1}+dp_{i-1,j,k,0}$

$dp_{i,j,k,1}=dp_{i,j-1,k-1,0}+dp_{i,j-1,k,1}$

注意先初始化 $(1,2)$ 和 $(2,1)$ 两个位置，因为第一步是可以向任意方向走的。

时间复杂度：$O(n^2k)$

Code:

#include<bits/stdc++.h>
using namespace std;
int T,n,m,dp[51][51][4][2],ans;
char ch[51][51];
int main()
{
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				cin>>ch[i][j];
				for(int k=0;k<=m;k++) dp[i][j][k][0]=dp[i][j][k][1]=0;
			}
	    }
	    for(int i=1;i<=n;i++){
	    	for(int j=1;j<=n;j++){
	    		if(ch[i][j]=='H') continue;
	    		else if(i==2&&j==1) dp[2][1][0][0]=1;
	    		else if(i==1&&j==2) dp[1][2][0][1]=1;
	    		else{
	    			for(int k=0;k<=m;k++){
	    			    if(i>=2&&j>=2&&k>=1){
	    			    	dp[i][j][k][0]+=dp[i-1][j][k-1][1];
	    			    	dp[i][j][k][1]+=dp[i][j-1][k-1][0];
	    			    }
	    			    if(i>=3) dp[i][j][k][0]+=dp[i-1][j][k][0];
	    			    if(j>=3) dp[i][j][k][1]+=dp[i][j-1][k][1];
	    		    }
	    		}
	    	}
	    }
	    ans=0;
	    for(int i=0;i<=m;i++) ans+=dp[n][n][i][0]+dp[n][n][i][1];
	    cout<<ans<<endl;
	}
	return 0;
}