原题链接:1541 - 小 X 学游泳(swim)-东方博宜OJ
题目描述
输入
输出
样例
输入
4 5
1 7 2 8 2
3 10 1 5 1
2 8 3 7 1
1 2 1 20 1
输出
19
说明
题解C++
最少步数问题,走到每个点的最小危险系数的和就是本题的最少步数
#include <bits/stdc++.h>
using namespace std;int n,m;
int a[50][50];
//走到每个点危险系数和的最小值
int d[50][50];
//方向值变化的数组
int fx[5] = {0,0,1,0,-1};
int fy[5] = {0,1,0,-1,0};//深搜求走到每个点经过的危险系数和的最小值
void dfs(int x,int y,int sum){d[x][y] = sum;//循环四方向 int tx,ty;for(int i = 1;i <= 4;i++){tx = x + fx[i];ty = y + fy[i];//如果该点可行:走到该点的危险系数的和更小//走到tx,ty点的危险系数 = 走到x,y点的危险系数 + tx,ty点的危险系数 if(sum+a[tx][ty]<d[tx][ty]){dfs(tx,ty,sum+a[tx][ty]);} }
} int main(){cin>>n>>m;for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){cin>>a[i][j];d[i][j] = INT_MAX; }}dfs(1,1,a[1][1]);cout<<d[n][m];return 0;
}