[USACODec21Bronze] Question 3「Walking Home」题解 | lightly salted = Potato Space = A place where I writes random shit :(

Bronze 确实都是简单题，我这种撒币都能做得来

# Method

考虑一个 dp[x][y][转弯次数][方向] 代表在这些条件下的合法路径数

转弯次数：路径上共有多少转弯处 ( $0$ ~ $k$ ，在此题中最高为 $3$ )
方向：上一个位置向当前位置前进的方向 ( $0/1$ $0 / 1$ )
- $0$ 为右， $1$ 为下
当上一个状态的方向与当前状态的方向不同时将转弯次数 $+1$
当前位置有障碍物时设为 $0$

同时这种方法需要进一步优化

将每一个在顶边或左边的块设为 $1$ 条 $0$ 次转弯的路径， $0$ 条其他转弯次数的路径

当顶边或左边中某一块为障碍物，将其右侧（顶边）或底部（左边）的块设为无路径可达

# Code

	int T, n, k, ans;
	int dp[100][100][4][2];
	int main() {
	read(T);
	while(T--) {
	ans = 0;
	read(n, k);
	for(int i = 1; i <= n; ++i) dp[1][i][0][0] = 1;
	for(int i = 1; i <= n; ++i) dp[i][1][0][1] = 1;
	for(int i = 1; i <= n; ++i) {
	for(int j = 1; j <= n; ++j) {
	char c = getchar();
	if(i == 1 \|\| j == 1) {
	if(c == 'H')
	if(i == 1)
	for(int l = j; l <= n; ++l) dp[i][l][0][0] = dp[i][l][0][1] = 0;
	else if(j = 1)
	for(int l = i; l <= n; ++l) dp[l][j][0][0] = dp[l][j][0][1] = 0;
	continue;
	}
	for(int l = 0; l <= k; ++l)
	if(!l) {
	dp[i][j][l][0] = dp[i][j - 1][l][0];
	dp[i][j][l][1] = dp[i - 1][j][l][1];
	} else if(c == '.') {
	dp[i][j][l][0] = dp[i][j - 1][l - 1][1] +
	dp[i][j - 1][l][0];
	dp[i][j][l][1] = dp[i - 1][j][l - 1][0] +
	dp[i - 1][j][l][1];
	} else if(c == 'H') dp[i][j][l][0] = dp[i][j][l][1] = 0;
	}
	getchar();
	}
	for(int i = 1; i <= k; ++i) ans += dp[n][n][i][0] + dp[n][n][i][1];
	writeln(ans);
	}
	}