题目描述 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了我好久…如果我的方法能给你点思路的说,那是最好的啦 ]]>
国庆节快乐!
同乐同乐