关于
联系
Oi大佬们
keyboard_arrow_down
本站已运行
载入天数...载入时分秒...
Woshiluo's Notebook
Woshiluo
2017年9月26日
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

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上,所以走这一块不用时间~

### 一周目


首先不得不吐槽这个银行哈,简直是无语了,起码也给人一幅地图吧,直接就乱走,你他妈当你是银行还是游乐园啊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是0,直接等于temp2
                if(temp2==0) {min_time[i][j]=temp;continue;}//同上
                if(temp<temp2) min_time[i][j]=temp;//如果都不为0尽心比较
                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!");
}

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

End


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


textsms