题目描述
猛兽侠中精灵鼠在利剑飞船的追逐下逃到一个n*n的建筑群中，精灵鼠从（0,0）的位置进入建筑群，建筑群的出口位置为（n-1,n-1），建筑群的每个位置都有阻碍，每个位置上都会相当于给了精灵鼠一个固定值减速，因为精灵鼠正在逃命所以不能回头只能向前或者向下逃跑，现在问精灵鼠最少在减速多少的情况下逃出迷宫？
输入描述:
第一行迷宫的大小: n >=2 & n <= 10000； 第2到n+1行，每行输入为以','分割的该位置的减速,减速f >=1 & f < 10。
输出描述:
精灵鼠从入口到出口的最少减少速度？
示例1
输入
3 5,5,7 6,7,8 2,2,4
输出
19
动态规划，初始化问题。
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
scanf("%d",&n);
int map[n][n];
int dp[n][n];
for( int i = 0 ; i < n ; i ++ ){
for( int j = 0 ; j < n-1 ; j ++ )
scanf("%d,",&map[i][j]);
scanf("%d",&map[i][n-1]);
}
dp[0][0]=map[0][0];
for( int i = 1 ; i < n ; i ++ )
dp[i][0] = map[i][0] + dp[i-1][0];
for( int j = 1 ; j < n ; j ++ )
dp[0][j] = dp[0][j-1] + map[0][j];
for( int i = 1 ; i < n ; i ++ )
for( int j = 1 ; j < n ; j ++ )
dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + map[i][j];
cout << dp[n-1][n-1] << endl;
return 0;
}
0 条评论