新手守护
541. 小 X 学游泳(swim)
问题描述
暑假快到啦，小 X 准备趁着这个暑假去学游泳。可是一开始小 X 就遇到了一个难题。
游泳池划分成了一个 �×�n×m 的方格， 这里 �×�n×m 表示 �n 行 �m 列。 因 为游泳池里的水深浅不一，所以这 �×�n×m 个方格对于小 X 的危险系数也会不一样。
而小 X 目前需要从左上角 的方格 (1,1)(1,1) 出发， 游到右下角 的方格 (�,�)(n,m)，小 X 每次只 能从当前方格游到上下左右四个相邻的方格中的某一格，并且在到达终点前不能离开游泳池。
小 X 很担心会发生什么危险，所以希望你能帮他找一条危险系数最小的路径。
一条路径的危险系数定义为这条路径所经过的方格的危险系数之和。
注意：这条路径不能经过同一个方格两次（小 X 当然不希望去那么危险的地方再游一次）
输入
输入数据第一行有两个用空格隔开的正整数 �n 和 �m， 表示泳池的行数和列数。
接下来共有 �n 行数据，每行有 �m 个用空格隔开的大于等于 00 的整数， 表示每个方格的危险系数
输出
输出仅有一行包含一个整数 ���ans ， 表示要求的从左上角的方格 (1,1)(1,1) 出发， 游到右下角的方格 (�,�)(n,m) 的最小的危险系数。
样例
输入
复制
4 5 1 7 2 8 2 3 10 1 5 1 2 8 3 7 1 1 2 1 20 1
输出
复制
19
说明
【数据范围】
对于 30%30% 的数据， 1≤�,�≤51≤n,m≤5
对于另外 40%40% 的数据， 1≤�,�≤201≤n,m≤20 ， 每个方格的危险系数 = 00 或 11
对于 100%100% 的数据， 1≤�,�≤301≤n,m≤30， 0≤0≤ 每个方格的危险系数 ≤100000≤100000
【样例解释】
路径： (1,1)(1,1) → (1,2)(1,2) → (1,3)(1,3) → (2,3)(2,3) → (2,4)(2,4) → (2,5)(2,5) → (3,5)(3,5) → (4,5)(4,5) ， 危险系数之和为 1+7+2+1+5+1+1+1=191+7+2+1+5+1+1+1=19 。
【来源】
常州市2016“信息与未来”夏令营选拔赛
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[30][30];
int dx[5]={0,0,1,0,-1};
int dy[5]={0,1,0,-1,0};
int mm[200][200];
void dfs(int x,int y,int c){
mm[x][y]=c;
int cx,cy;
for(int i=1;i<=4;i++){
cx=x+dx[i];
cy=y+dy[i];
if(c+a[cx][cy]<mm[cx][cy]&&cx<=n&&cx>=1&&cy>=1&&cy<=m){
dfs(cx,cy,c+a[cx][cy]);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
mm[i][j]=21e8;
}
}
dfs(1,1,a[1][1]);
cout<<mm[n][m];
return 0;
}
这代码最后一个点过不去，运行错误
求指点！！！
