每日“亿“题 东方博宜OJ 1541 - 小 X 学游泳(swim)
原题链接：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;
}