二维dp-地图

问题描述

传说，在蓝桥王国中一个极其神秘的森林。这个森林的起点在(1,1) ，终点在 (n,m)。在你进入这个森岭后，每次你只可以向下或者向右走，由于森岭的神秘力量，至多只可以改变 k 次方向。

小蓝现在想知道，一共有多少种方案可以从(1,1) 进入然后从 (n,m) 走出。数据保证至少存在一种方案。

输入格式

第 1 行包含三个正整数 n,m,k，分别表示地图的规模和可以改变方向的次数。

第 2 到 n+1 行包含 m 个字符，表示地图上该位置的信息，用.表示空地，#表示石头无法通行，保证起点和终点不为石头。

输出格式

输出共 1 行，包含 1 个整数，表示方案数。

样例输入

3 3 1
...
.#.
...

样例输出

2

评测数据规模

对于所有评测数据，1≤n,m≤100，1≤k≤5。

题解

dp[i][j][k][0]表示在位置(i, j)处，转向了k次，方向向下的方案数

dp[i][j][k][1]表示在位置(i, j)处，转向了k次，方向向右的方案数

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 105;char mp[N][N];int dp[N][N][10][2];// 表示到位置(i, j)转向了k次，方向为0(向下)， 1(向右)int n,m, k;int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m >> k;for(int i = 1;i <= n;i ++)for(int j = 1;j <= m;j ++)cin >> mp[i][j];dp[1][1][0][0] = 1;dp[1][1][0][1] = 1;for(int i = 2;i <= m;i ++)if(mp[1][i] == '.')dp[1][i][0][1] = dp[1][i - 1][0][1];for(int i = 2;i <= n;i ++)if(mp[i][1] == '.')dp[i][1][0][0] = dp[i - 1][1][0][0];for(int i = 2;i <= n;i ++)for(int j = 2;j <= m;j ++)if(mp[i][j] == '.')for(int l = 1;l <= k;l ++){dp[i][j][l][0] = (dp[i - 1][j][l][0] + dp[i - 1][j][l - 1][1]);dp[i][j][l][1] = (dp[i][j - 1][l][1] + dp[i][j - 1][l - 1][0]);}ll ans = 0;for(int l = 0;l <= k;l ++){if(n == 1 && m == 1){ans = 0;break;}ans += dp[n][m][l][0] + dp[n][m][l][1];}cout << ans << '\n';return 0;
}