5467: 【搜索】流浪奶牛

题目描述

吃不到饭的奶牛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:

#include<bits/stdc++.h>
using namespace std;
int r,c,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},ans=INT_MAX;
char mp[1005][1005];
int a[1005][1005];
bool vis[1005][1005];
void dfs(int x,int y,int step){if(x==r&&y==c){ans=min(ans,step);}for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(xx>=1&&yy>=1&&xx<=r&&yy<=c&&vis[xx][yy]==false&&step+1+a[xx][yy]<ans){vis[xx][yy]=1;dfs(xx,yy,step+1+a[xx][yy]);vis[xx][yy]=0;}}
}
int main(){cin>>r>>c;for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){cin>>mp[i][j];a[i][j]=mp[i][j]-'0';}}vis[1][1]=true;dfs(1,1,0);cout<<ans;return 0;
}