首页 > 代码库 > codevs——T1337 银行里的迷宫

codevs——T1337 银行里的迷宫

 时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 白银 Silver
 
 
 
题目描述 Description

       楚楚每一次都在你的帮助下过了一关又一关(比如他开宴会)。这一次,你的才华让楚楚被劫住了!(好心办了坏事啊,下次不理他了=_=)

       歹徒: hehe~

       楚楚:(冷汗ing)干啥^_^!(PS:现在还笑得出来!!!)

       歹徒:抢劫的说~

       楚楚:你们想干啥!!(PS:不是告诉你了,是抢劫~)

       歹徒:这里是银行的陷阱,也就是一个迷宫……你要带我们离开这里……否则……

       楚楚:(想:那你是咋抓到我的,郁闷)好吧……

       楚楚认为生命还是最重要的……(大不了出去以后找警察……)

       于是,他认命了……

       他从歹徒口中得知这是一个方形的迷宫(歹徒老大:你还要啥形状的,跟我说一声!),他们的位置是[1,1],要走到[n,m],长是n,宽是m,这是一个很大的迷宫,里面有陷阱(小明:能不能踩进去的,说!楚楚:当然不能,不过可以用轻功,多花一秒蓄力~用轻功走过的陷阱会石化,变成路,而且刚好走过~ 歹徒想:虾米轻功~明明是杀人利器~还好没和他打起来~),还有墙(PS:说一声,墙不能穿过,虽有轻功,但是还是过不去墙,这个墙也是银行的秘密~即使你是神犇也不行哦~ 楚楚:又坑我~)。(小明:路呢? 楚楚:废话,当然有,只不过这是银行机密,不能说!)

       楚楚想在最短时间里走出迷宫(小明:否则歹徒会发怒的,对不对? 楚楚:废话!),若是超过了歹徒老大的忍耐时间time,那就……

       (楚楚:小明……SOS,别忘了帮我报警!! 传呼机:嘀,嘀,嘀…… 楚楚:咋么可以这样!可恶!)于是,他顺便还要去找电话报个警(报警不需要时间,打通即可。且电话机可能有多个,但也没有可能没有~)。

楚楚:我的预感告诉我,这个迷宫只能向右或下走~郁闷了~

输入描述 Input Description

       第1行是n,m, time,三个整数。

       第2到n+1行每行有m个字母(有大写也有小写的)(楚楚:歹徒真笨~,就不能翻译一下吗~)。

       字母解析:T(t)是陷阱,W(w)是墙,R(r)是路,A(a)是电话~ (遇到不认识的字符就~算之为路!)

输出描述 Output Description

       仅一行走出迷宫的最小时间t(走一步要一秒的说),不能在规定时间走出迷宫,或者打不了电话,请输出“Oh my god!”(不包括引号)。

样例输入 Sample Input

3 3 100

RRR

WWA

TRR

样例输出 Sample Output

4

数据范围及提示 Data Size & Hint

时间限制 Time Limitation

各个测试点1s

注释 Hint

       10%的数据 n≤20,m≤20

100%的数据 n≤500,m≤500,time≤100000,不保证[1,1]或者[n,m]不是墙的说,且若[1,1]或者[n,m]不是路,那么就不能活着回去了……

数据解析:

由于楚楚一开始就站在1,1上,所以走这一块不用时间~

 

标签是 深搜,正解是DP~~不吐槽了

首先特判起点和终点的情况

然后用f[i][j]表示到达map[i]j[j]的步数,如果是T就多加1

如果不越界并且,前面的步数少,就说明是从前面走过来的

if(i>1&&f[i][j]>f[i-1][j]) f[i][j]=min(f[i][j],f[i-1][j]+1);
if(j>1&&f[i][j]>f[i][j-1]) f[i][j]=min(f[i][j],f[i][j-1]+1);

 

 1 #include <iostream> 2 #include <cstdio> 3 #define min(a,b) (a<b?a:b) 4 using namespace std; 5  6 const int MAX(25000000); 7 const int N(500+15); 8 int n,m,t,map[N][N]; 9 int f[N][N],called;10 11 int main()12 {13     scanf("%d%d%d",&n,&m,&t);14     for(int i=1;i<=n;i++)15     {16         for(int j=1;j<=m;j++)17             scanf(" %c",&map[i][j]),map[i][j]=toupper(map[i][j]);18     }        19     if(map[1][1]==W||map[1][1]==T||map[n][m]==W||map[n][m]==T)20     {21         printf("Oh my god!");22         return 0;23     }        24     for(int i=1;i<=n;i++)25         for(int j=1;j<=m;j++)26         {27             if(i==1&&j==1) continue;28             f[i][j]=MAX;29             if(map[i][j]==W) continue;30             if(map[i][j]==A) called=1;31             if(i>1&&f[i][j]>f[i-1][j])32                 f[i][j]=min(f[i][j],f[i-1][j]+1);33             if(j>1&&f[i][j]>f[i][j-1])34                 f[i][j]=min(f[i][j],f[i][j-1]+1);35             if(map[i][j]==T) f[i][j]++;36         }37     if(called&&f[n][m]<=t) printf("%d",f[n][m]);38     else printf("Oh my god!");39     return 0;40 }

 

codevs——T1337 银行里的迷宫