我要上蓝翔

描述

在一个山沟里，姐弟俩同时考上了大学。但由于家里拮据，所以这并不是什么好消息。父亲对孩子说：我就是砸锅卖铁也要把你们姐俩供出来。 当时的姐姐已经决定放弃上学的机会。 没想到第二天天还没亮，弟弟就偷偷带著几件破衣服和几个乾巴馒头走了，在姐姐枕边留下一个纸条： 姐,你别愁了，考上大学不容易，我出去打工供你。弟。 姐姐握著那张字条,趴在炕上,失声痛哭。 那一年，弟弟17岁，姐姐20岁。 姐姐用父亲满村子借的钱和弟弟在工地裏搬水泥挣的钱终於读到了大三。 一天姐姐正在寝室里看书,同学跑进来对姐姐说，有个老乡在找你。姐姐很纳闷，走出去后，远远地看见弟弟,穿著满身是水泥和沙子的工作服。姐姐说，你怎么和我同学说你是我老乡啊? 他笑著说，你看我穿的这样，说是你弟，你同学还不笑话你？ 姐姐鼻子一酸，眼泪就落了下来。弟弟赶忙为姐姐擦掉眼泪，说：姐，你别哭，我这次来是想让你帮我打听一下，学挖掘机哪家强？ 

 

在你的帮助下，弟弟踏上了去蓝翔的路。

那么问题就来了。

输入

第一个数T，T组测试数据。
两个数 n, m; ( 0< n , m <= 100 ) 表示一个h行m列的二维地图。
接下来n行每行m 个字符。
‘s’ 表示弟弟目前所在位置。
‘# ’表示此处为一座山。为了节省体力，不从此处通行。
从‘A’-‘Z’表示各地的经济水平，对应1-26，路过对应字符的地区需要交对应的生活费。
‘l’表示蓝翔技校的所在地。
s 与 l 均为小写字母。
弟弟只能走四个方向。

输出

输出一个数表示弟弟到达蓝翔需要的生活费最小是多少。
如果不能到达，输出 -1。

样例输入

3
3 5
#sVGF
A##ZA
lCDBC
3 3
sAB
ABS
ABl
3 3
s#B
###
ABl

样例输出

48
4
-1

题解：两种方法，dfs超时，dfs刚开始错了好长时间，对不上答案。。。导致对做搜索题产生了恐惧。。。

bfs代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<queue>
 4 const int MAXN=110;
 5 using namespace std;
 6 struct Node{
 7     int x,y,step;
 8     friend bool operator < (Node a,Node b){
 9         return a.step>b.step;
10     } 
11 };
12 char map[MAXN][MAXN];
13 int vis[MAXN][MAXN];
14 int disx[4]={0,0,1,-1};
15 int disy[4]={1,-1,0,0};
16 int n,m;
17 void bfs(int sx,int sy){
18     priority_queue<Node>dl;
19     Node a,b;
20     memset(vis,0,sizeof(vis));
21     a.x=sx;a.y=sy;a.step=0;
22     dl.push(a);
23     while(!dl.empty()){
24         a=dl.top();
25         vis[a.x][a.y]=1;
26         dl.pop();
27         for(int i=0;i<4;i++){
28             b.x=a.x+disx[i];b.y=a.y+disy[i];
29             b.step=a.step;
30             if(b.x<0||b.y<0||b.x>=n||b.y>=m||vis[b.x][b.y]||map[b.x][b.y]==‘#‘)continue;
31             if(map[b.x][b.y]>=‘A‘&&map[b.x][b.y]<=‘Z‘)b.step+=map[b.x][b.y]-‘A‘+1;
32             if(map[b.x][b.y]==‘l‘){
33                 printf("%d\n",b.step);
34                 return ;
35             }
36             dl.push(b);
37         }
38     }
39     puts("-1");
40 }
41 int main(){
42     int T;
43     scanf("%d",&T);
44     while(T--){
45         scanf("%d%d",&n,&m);
46         for(int i=0;i<n;i++)scanf("%s",map[i]);
47         int sx,sy;
48         for(int i=0;i<n;i++)
49             for(int j=0;j<m;j++)
50                 if(map[i][j]==‘s‘)sx=i,sy=j;
51         bfs(sx,sy);
52     }
53     return 0;
54 }

dfs超时代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define MIN(x,y) (x<y?x:y)
 4 const int INF=0x3f3f3f3f;
 5 int n,m,k,ans;
 6 char map[110][110];
 7 int disx[4]={1,-1,0,0};
 8 int disy[4]={0,0,1,-1};
 9 int vis[110][110];
10 int sx,sy,temp;
11 void dfs(int x,int y,int t){
12     if(map[x][y]==‘l‘){
13         ans=MIN(ans,t-(‘l‘-‘A‘+1));
14         return;
15     }
16 //  printf("%d",t);
17     for(int i=0;i<4;i++){
18         int nx=x+disx[i];int ny=y+disy[i];//nx,ny应该局部变量。。。。。。。。。 
19         if(vis[nx][ny]||nx<0||ny<0||nx>=n||ny>=m||map[nx][ny]==‘#‘||t>ans)continue;
20         vis[nx][ny]=1;
21         dfs(nx,ny,t+map[nx][ny]-‘A‘+1);
22         vis[nx][ny]=0;
23     }
24     return;
25 }
26 void initial(){
27     memset(vis,0,sizeof(vis));
28     memset(map,0,sizeof(map));
29     ans=INF;
30 }
31 int main(){
32     int T;
33     scanf("%d",&T);
34     while(T--){
35         scanf("%d%d",&n,&m);
36         int flot=0;
37         initial();
38         for(int i=0;i<n;i++)scanf("%s",map[i]);
39         for(int i=0;i<n;i++)for(int j=0;j<m;j++){
40             if(map[i][j]==‘s‘)sx=i,sy=j;
41         }
42         map[sx][sy]=‘#‘;
43         dfs(sx,sy,0);
44         if(ans==INF)puts("-1");
45         else printf("%d\n",ans);
46     }
47     return 0;
48 }

 

 

我要上蓝翔

原文：http://www.cnblogs.com/handsomecui/p/4839483.html