Codevs:1337 银行里的迷宫

题目描述 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)是电话~ (遇到不认识的字符就~算之为路！)

样例输入 Sample Input

3 3 100 RRR WWA TRR

样例输出 Sample Output

数据范围及提示 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上，所以走这一块不用时间~ ###　一周目

首先不得不吐槽这个银行哈，简直是无语了，起码也给人一幅地图吧，直接就乱走，你他妈当你是银行还是游乐园啊wocccc…… 这道题看起来简直就是一道赤裸裸的dfs啊,于是乎你们的博主使用直接递归dfs

#include <cstdio>
#include <cstring>
using namespace std;
int time,now_use_time,a[30][30],min_time=0x7fffffff,m,n;
void dfs(int x,int y){
    if(x==m-1&&y==n-1) {
        if(now_use_time<min_time)min_time=now_use_time;
        return ;
    }
    if(now_use_time>time) return;
    if(a[x+1][y]==2&&y<m&&x+1<n){
        now_use_time+=2;
        dfs(x+1,y);
    }
    if(a[x+1][y]==0&&y<m&&x+1<n){
        now_use_time+=1;
        dfs(x+1,y);
    }
    if(a[x][y+1]==2&&y+1<m&&x<n){
        now_use_time+=2;
        dfs(x,y+1);
    }
    if(a[x][y+1]==0&&y+1<m&&x<n){
        now_use_time+=1;
        dfs(x,y+1);
    }
}
int main(){
    scanf("%d %d %d",&n,&m,&time);
    for(int i=0;i<n;i++){
            char temp[30];
            scanf("%s",temp);
            for(int j=0;j<m;j++){
                if(temp[j]=='t'||temp[j]=='T') a[i][j]=2;
                else if(temp[j]=='w'||temp[j]=='W') a[i][j]=3;
                else a[i][j]=0;
            }
    }
    if(a[n][m]==3||a[0][0]==3){
        printf("Oh my god!");
        return 0;
    }
    dfs(0,0);
    if(min_time<0x7fffffff) printf("%d",min_time);
    else printf("Oh my god!");
}

结果呢，直接一个二十分——##### TLE （我的心是悲痛欲绝的更不要提数组开小了的问题了（装死

二周目

既然不能递归，我们就直接暴力循环

/*
作者:Woshiluo
题目:p1337 银行里的迷宫
*/
/*
//如何写一份可以提交的代码？以P1000 A+B为例
#include <iostream>
using namespace std;
int main()
{
    int a, b; //定义两个变量名
    cin >> a >> b; //从标准输入流中输入两个整数
    cout << a + b << endl; //输出到标准输出流中
}
// 完成程序以后，点击下方的提交，即可看到测试结果
*/
#include <cstdio>
using namespace std;
char temp[510][510];//输入数组
int a[510][510],z[510][510],min_time[510][510];//a数组表示通过所需时间,z数组表示当前格子是否能通过,min_time表示每个格子所需的最少时间
int main(){
    int n,m,time;
    scanf("%d %d %d",&n,&m,&time);
    for(int i=0;i<n;i++){
        scanf("%s",temp[i]);//输入
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(temp[i][j]=='T'||temp[i][j]=='t') {
                a[i][j]=2;//陷阱
            }
                else if(temp[i][j]=='A'||temp[i][j]=='a'){
                a[i][j]=1;//电话
                z[i][j]=0;//实际上就是一绕人条件，跟路一样的功能
            }
            else if(temp[i][j]=='W'||temp[i][j]=='w'){
                a[i][j]=3;//墙
                z[i][j]=-1;
            }
            else a[i][j]=1;//路（因为题目说了，遇到不知道的字符，算之为路（2333
        }
    }
    if(a[0][0]!=1||a[n-1][m-1]!=1){ printf("Oh my god!");return 0;}//如果起点和终点任意一个是墙，直接跳出
    z[0][0]=0;//无畏的工作
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(z[i][j]==-1)continue;//如果当前格子无法通过则越过
            int temp=0,temp2=0;
            bool bl=false;//判断是否已经有值可以填充进入min_timr
            if(z[i-1][j]!=-1&&i-1>=0){//向上搜寻
                temp=min_time[i-1][j]+a[i][j];
                bl=true;
                if(min_time[i-1][j]==0){
                    if(i-1!=0)temp=0;
                    if(j!=0)temp=0;
                }
            }
            if(z[i][j-1]!=-1&&j-1>=0){//向左搜寻
                temp2=min_time[i][j-1]+a[i][j];
                bl=true;
                if(min_time[i][j-1]==0){
                    if(i!=0)temp2=0;
                    if(j-1!=0)temp2=0;
                }
            }
            if(bl){
                if(temp==0) {min_time[i][j]=temp2;continue;}// 如果temp是０，直接等于temp2
                if(temp2==0) {min_time[i][j]=temp;continue;}//同上
                if(temp<temp2) min_time[i][j]=temp;//如果都不为０尽心比较
                else min_time[i][j]=temp2;
            }
        }
    }
    if(min_time[n-1][m-1]!=0&&min_time[n-1][m-1]<time) printf("%d",min_time[n-1][m-1]);//如果存在即输出
    else printf("Oh my god!");
}

这个方法说白了就是讲每一个格子的上方格子与左方格子进行搜寻，寻找出其中最小的，确保每一步都是最优的，知道最后一步，如果最后一步是０，那就嗝屁了… （有种动归的感觉

End

这道题目Ａ了我好久…如果我的方法能给你点思路的说，那是最好的啦 ]]>