迷宫

题目：

输入样例：

3 1 1
1 2 3
4 5 6
7 8 9
2 2 1
3 1 R

输出样例：

21

思路：

题目大意：给定一个n x m的平面网格，并且每一个格子都有一定的代价，并且设有障碍物和陷阱，障碍物的意思是会在原来对应格子的基础上在加上一定的代价，陷阱的意思是如果移动到某一位置有陷阱存在，那么会自动在向右或下移动两个格子。要求从(0, 0)位置开始进行移动，移动到(n, m)结束，每次移动只能选择向下或者向右移动。求移动到终点时最小的代价是什么。

看到题目的数据范围 0 < n,m < 1001就知道，这道题不能使用纯暴力的方法进行求解n * m大概在$10^6$左右，如果时间复杂度在$O(N^2)$或者$O(N\log N)$就可能过不了全部数据。

这道题与力扣上的不同路径II问题十分相似，只是不同路径II问题求的是有多少不同路径的可能性，这道题是求最小的代价是什么，另一点不同的是这道题设定的障碍物与陷阱，而不同路径问题仅仅只设定了障碍物，并且要求有障碍物的位置不能通过（友情链接：不同路径 II）

整体思路：使用动态规划的思想，在处理输入数据的时候，将障碍物的部分的代价直接累加到原数组上去，并且开辟一个新的字符数组，用来记录那个地方有陷阱。

初始化边界：

将dp[0][0]初始化为第一个格子的代价，然后第一行其它位置的dp值等于前一个位置的dp值加上该位置的代价值，第一列其它位置的dp值等于上面一个位置的dp值加上当前位置的代价值。

代码如下：

for(int i = 1;i <= n;i ++) dp[i][1] = dp[i - 1][1] + nums[i][1];
for(int j = 1;j <= m;j ++) dp[1][j] = dp[1][j - 1] + nums[1][j];

递推公式：

由于每一个位置都可能由其上面的一个位置或者左面的一个位置移动而来，因此dp的值可以初定为（前面一个位置的dp值与上面一个位置的dp值的最小值）+ 当前位置的代价。

代码如下：

dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + nums[i][j];

又因为有陷阱的存在，所以能够道达该位置的可能还有从上面两个位置移动而来，或者从前面两个位置移动而来，因此需要进行额外考虑。

如果存在从上面移动而来的可能，那么就在当前dp值的基础上进行判断，取当前位置上的dp值与（上面两格位置的dp值 +上面一格位置的代价值 + 当前位置的代价值）的最小值，即为当前位置的最小值。因为我们首先判断了正常情况时该位置的dp值，由于存在特殊情况，我们需要取正常情况与特殊情况的最小值来作为当前位置的dp值。

同理，如果当前位置存在从左边两个位置到来的可能，与上面两个位置到来的情况类似。

注意：题目说明不可能一个位置存在两种陷阱的可能。

代码如下：

dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + nums[i][j];
// 判断特殊情况
if(i > 2 &&cnt[i - 2][j] == 'D'){  // 表示从上边过来的 
	dp[i][j] = min(dp[i][j], dp[i - 2][j] + nums[i - 1][j]+ nums[i][j]) ;
}else if(j > 2  && cnt[i][j - 2] == 'R'){  // 表示从左边过来的
	dp[i][j] = min(dp[i][j], dp[i][j - 2] + nums[i][j - 1] + nums[i][j]);

代码：

// 迷宫——动态规划版本
#include<bits/stdc++.h>
using namespace std;


void solve(){
	int n, m, k, p;cin>>n>>m>>k>>p;   // k个格子中设置了障碍物, p个陷阱
	vector<vector<int>> nums(n + 10, vector<int>(m + 1, 0));
	vector<vector<char>> cnt(n + 10, vector<char>(m + 1, '0'));   // 用于记录 
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			cin>>nums[i][j];
		}
	}
	while(k--){  // 设置k个障碍物   直接在原有的成本上进行添加成本即可 
		int _x, _y, c;cin>>_x>>_y>>c;
		 nums[_x][_y] += c;
	}
	while(p--){  // 设置p个陷阱 
		int _x, _y;
		char c;
		cin>>_x>>_y>>c;
		cnt[_x][_y] = c;    // 如果是D：向下移动两个格子，如果是R：向右移动两个格子 
	}
	// 动态规划
	const int inf = 0x3f3f3f3f;
	vector<vector<int>> dp(n + 10, vector<int>(m + 10, 0));

	// 初始化边界
	for(int i = 1;i <= n;i ++) dp[i][1] = dp[i - 1][1] + nums[i][1];
	for(int j = 1;j <= m;j ++) dp[1][j] = dp[1][j - 1] + nums[1][j];
//	dp[1][1] = nums[1][1];
	for(int i = 2;i <= n;i ++){
		for(int j = 2;j <= m;j ++){
//			if(i == 1 && j == 1)continue;
			dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + nums[i][j];
			// 判断特殊情况
			 if(i > 2 &&cnt[i - 2][j] == 'D'){  // 表示从上边过来的 
			 	dp[i][j] = min(dp[i][j], dp[i - 2][j] + nums[i - 1][j]+ nums[i][j]) ;
			 }else if(j > 2  && cnt[i][j - 2] == 'R'){  // 表示从左边过来的
			 	dp[i][j] = min(dp[i][j], dp[i][j - 2] + nums[i][j - 1] + nums[i][j]);
			 }
		}
	}
	cout<<dp[n][m]<<endl;
	return ;
}


int main(){
	ios::sync_with_stdio(0) ;
	cin.tie(0);
	int t = 1;
	while(t--){
		solve();
	}
	return 0;
}