233
技術社區[雲棲]
WIKIOI-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)是電話~ (遇到不認識的字符就~算之為路！)
輸出描述 Output Description
僅一行走出迷宮的最小時間t(走一步要一秒的說)，不能在規定時間走出迷宮，或者打不了電話，請輸出“Oh my god!”(不包括引號)
。
樣例輸入 Sample Input
3 3 100
RRR
WWA
TRR
樣例輸出 Sample Output
4
//遞歸超時代碼
#include<stdio.h>
#include<algorithm>
using namespace std;
char a[550][550];
int b[5000];
int endx,endy,phone,k=0,flag=0;
void Found(int x,int y,int sum)
{
if(flag==1)
return;
if(a[x][y]=='W'||a[x][y]=='w')
return;
if(a[x][y]=='A'||a[x][y]=='a')
phone=1;//這裏判斷不清晰
if(!(x==1&&y==1))
{
if(a[x][y]=='T'||a[x][y]=='t')
sum+=2;
else
sum++;
}
if(x==endx&&y==endy)
{b[k++]=sum;flag=1;return;}
if(y+1<=endy) Found(x,y+1,sum);
if(x+1<=endx) Found(x+1,y,sum);
if(y-1>=1) Found(x,y-1,sum);
if(x-1>=1) Found(x-1,y,sum);
}
int main()
{
int i,j,n,m,time;
scanf("%d%d%d",&n,&m,&time);
getchar();
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%c",&a[i][j]);
}
if(i!=n)
getchar();
}
//若[1,1]或者[n,m]不是路，那麼就不能活著回去了
if((a[1][1]=='W'||a[1][1]=='w')||(a[n][m]=='W'||a[n][m]=='w'))
printf("Oh my god!\n");
else
{
endx=n;endy=m;phone=0;
Found(1,1,0);
sort(b,b+k);
if(b[0]<=time&&phone==1)
printf("%d\n",b[0]);
else
printf("Oh my god!\n");
}
return 0;
}
AC代碼：
//動態規劃，由已知步數求未知步數 (參考，源代碼屬於“憶_碎碎念”)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cctype>
#include <climits>
using namespace std;
#define BIGNUM 25000000
char str[505][505];
int dp[505][505];
int n, m, limit;
bool phone = false;
int main()
{
scanf("%d%d%d", &n, &m, &limit);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
scanf(" %c", &str[i][j]);
str[i][j] = toupper(str[i][j]);
}
if(str[1][1] == 'W' || str[n][m] == 'W' || str[1][1] == 'T' || str[n][m] == 'T')
{
printf("Oh my god!");
exit(0);
}
else
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(i == 1 && j == 1)//起點不做計算
continue;
dp[i][j] = BIGNUM;//賦值為很大的值，為了便於後麵計算步數
if(str[i][j] == 'W')//碰見牆就不做計算 ，直接返回
continue;
if(str[i][j] == 'A')
phone = true//有一次出現電話了就標記一下
//因為題設隻有兩種走法，向下或向右，那麼假如到了一個坐標，那麼隻能從左邊過來或者是從上邊過來
//隻要現在的遠遠大於原來的，就說明原來可能從那裏經過，所以本格加上次的時間再加一次這次的時間
//就是 dp[i][j] = dp[i - 1][j] + 1;或 dp[i][j] = dp[i][j - 1] + 1;
//如果是陷阱就要多加一次 dp[i][j]++;
if(i - 1 >= 1 && dp[i - 1][j] < dp[i][j])
dp[i][j] = dp[i - 1][j] + 1;
if(j - 1 >= 1 && dp[i][j - 1] < dp[i][j])
dp[i][j] = dp[i][j - 1] + 1;
if(str[i][j] == 'T')
dp[i][j]++;
}
}
}
if(phone && dp[n][m] <= limit)
printf("%d", dp[n][m]);
else
printf("Oh my god!");
return 0;
}
最後更新：2017-04-03 12:55:26