网页设计网站欣赏,网站建设与运营公司的市场开发方案,湖南省郴州市天气预报,如何做vip电影解析网站题目描述
吃不到饭的奶牛Bessie一气之下决定离开农场#xff0c;前往阿尔费茨山脉脚底下的农场#xff08;听说那儿的草极其美味#xff09;投靠她的亲戚Jimmy。但是前往目的地的山路崎岖#xff0c;Bessie又没有吃饭#xff0c;她需要尽量保存体力#xff0c;以最轻松的…题目描述
吃不到饭的奶牛Bessie一气之下决定离开农场前往阿尔费茨山脉脚底下的农场听说那儿的草极其美味投靠她的亲戚Jimmy。但是前往目的地的山路崎岖Bessie又没有吃饭她需要尽量保存体力以最轻松的方式到达农场。
此刻Bessie 位于坐标为 (1,1) 的区域并想到坐标为 (r,c) 的农场。她知道以她所在的区域为起点每次移动至相邻的四个区域之一且会消耗1点体力值同时翻越陡峭的山路需要消耗x点体力值。
输入
第一行两个整数 r,c。
接下来 r 行每行 c 个范围0~9的数字x表示 Bessie 翻越该地需要消耗的体力值。(注意起点和终点一定为0)
输出
1行输出Bessie的最少体力消耗
样例输入
2 2
01
20
样例输出
3
Code:
#includebits/stdc.h
using namespace std;
int r,c,dx[4]{0,0,1,-1},dy[4]{1,-1,0,0},ansINT_MAX;
char mp[1005][1005];
int a[1005][1005];
bool vis[1005][1005];
void dfs(int x,int y,int step){if(xryc){ansmin(ans,step);}for(int i0;i4;i){int xxxdx[i],yyydy[i];if(xx1yy1xxryycvis[xx][yy]falsestep1a[xx][yy]ans){vis[xx][yy]1;dfs(xx,yy,step1a[xx][yy]);vis[xx][yy]0;}}
}
int main(){cinrc;for(int i1;ir;i){for(int j1;jc;j){cinmp[i][j];a[i][j]mp[i][j]-0;}}vis[1][1]true;dfs(1,1,0);coutans;return 0;
}
