題目描述

吃不到飯的奶牛Bessie一氣之下決定離開(kāi)農(nóng)場(chǎng)，前往阿爾費(fèi)茨山脈腳底下的農(nóng)場(chǎng)（聽(tīng)說(shuō)那兒的草極其美味）投靠她的親戚Jimmy。但是前往目的地的山路崎嶇，Bessie又沒(méi)有吃飯，她需要盡量保存體力，以最輕松的方式到達(dá)農(nóng)場(chǎng)。

此刻，Bessie 位于坐標(biāo)為?(1,1)?的區(qū)域，并想到坐標(biāo)為?(r,c)?的農(nóng)場(chǎng)。她知道，以她所在的區(qū)域?yàn)槠瘘c(diǎn)，每次移動(dòng)至相鄰的四個(gè)區(qū)域之一且會(huì)消耗1點(diǎn)體力值，同時(shí)翻越陡峭的山路需要消耗x點(diǎn)體力值。

輸入

第一行兩個(gè)整數(shù)?r,c。

接下來(lái)?r?行，每行?c?個(gè)范圍0~9的數(shù)字x，表示 Bessie 翻越該地需要消耗的體力值。(注意，起點(diǎn)和終點(diǎn)一定為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;
}