題目：
題目描述 Description
楚楚每一次都在你的幫助下過了一關又一關(比如他開宴會)辜窑。這一次，你的才華讓楚楚被劫住了旺垒！(好心辦了壞事啊，下次不理他了==)
歹徒： hehe~
楚楚：(冷汗ing)干啥^^肤无！(PS：現(xiàn)在還笑得出來Ｏ冉！宛渐！)
歹徒：搶劫的說~
楚楚：你們想干啥＞貉！(PS：不是告訴你了窥翩，是搶劫~)
歹徒：這里是銀行的陷阱,也就是一個迷宮……你要帶我們離開這里……否則……
楚楚：(想：那你是咋抓到我的业岁，郁悶)好吧……
楚楚認為生命還是最重要的……(大不了出去以后找警察……)
于是，他認命了……
他從歹徒口中得知這是一個方形的迷宮(歹徒老大：你還要啥形狀的寇蚊，跟我說一聲笔时！)，他們的位置是[1,1]仗岸，要走到[n,m],長是n允耿，寬是m，這是一個很大的迷宮爹梁，里面有陷阱(小明：能不能踩進去的右犹，說！楚楚：當然不能姚垃，不過可以用輕功念链，多花一秒蓄力用輕功走過的陷阱會石化，變成路积糯，而且剛好走過 歹徒想：蝦米輕功明明是殺人利器還好沒和他打起來)掂墓，還有墻(PS：說一聲，墻不能穿過看成，雖有輕功君编，但是還是過不去墻，這個墻也是銀行的秘密即使你是神犇也不行哦~ 楚楚：又坑我~)川慌。(小明：路呢吃嘿？ 楚楚：廢話，當然有梦重，只不過這是銀行機密兑燥，不能說！)
楚楚想在最短時間里走出迷宮(小明：否則歹徒會發(fā)怒的琴拧，對不對降瞳？ 楚楚：廢話！)蚓胸，若是超過了歹徒老大的忍耐時間time挣饥，那就……
(楚楚：小明……SOS除师，別忘了幫我報警！扔枫！ 傳呼機：嘀汛聚，嘀，嘀…… 楚楚：咋么可以這樣茧吊！可惡贞岭！)于是，他順便還要去找電話報個警(報警不需要時間搓侄，打通即可瞄桨。且電話機可能有多個，但也沒有可能沒有~)讶踪。
楚楚：我的預感告訴我芯侥，這個迷宮只能向右或下走郁悶了
輸入描述 Input Description
第1行是n,m, time，三個整數(shù)乳讥。
第2到n+1行每行有m個字母(有大寫也有小寫的)(楚楚：歹徒真笨柱查，就不能翻譯一下嗎)。
字母解析：T(t)是陷阱云石，W(w)是墻唉工，R(r)是路，A(a)是電話~ (遇到不認識的字符就~算之為路汹忠！)
輸出描述 Output Description
僅一行走出迷宮的最小時間t(走一步要一秒的說)淋硝，不能在規(guī)定時間走出迷宮，或者打不了電話宽菜，請輸出“Oh my god!”(不包括引號)谣膳。
樣例輸入 Sample Input
3 3 100
RRR
WWA
TRR
樣例輸出 Sample Output
4
數(shù)據(jù)范圍及提示 Data Size & Hint
時間限制**** Time Limitation
各個測試點1s
**注釋**** Hint******
10%的數(shù)據(jù) n≤20,m≤20
100%的數(shù)據(jù) n≤500,m≤500,time≤100000,不保證[1,1]或者[n,m]不是墻的說,且若[1,1]或者[n,m]不是路，那么就不能活著回去了……
數(shù)據(jù)解析：
由于楚楚一開始就站在1,1上铅乡，所以走這一塊不用時間~
此題是一道走迷宮的題继谚，可以先判定第一個和最后一個的情況，如果不是路就死阵幸。
之后我們可以用一個數(shù)組表示到當前為止共走了多少秒（此題只能向下或向右走）花履，注意遇到陷阱可以走，但需要多加1s.
遇到電話就計數(shù)挚赊。
最后判定時間和有無電話即可臭挽。
參考代碼：
#include <iostream>
#include <cstring>
using namespace std;
char map[505][505];
int dp[505][505];
void setmap(char map[][505],int n,int m) {
for (int i = 0;i < n;++i) {
for (int j = 0;j < m;++j) {
cin >> map[i][j];
}
}
}
int flag;
void dfs(int i,int j,int n,int m,int time) {
for (int i = 0;i < n;++i) {
for (int j = 0;j < m;++j) {
if (i == 0 && j == 0) continue;
dp[i][j] = 99999;
if (map[i][j] == 'W' || map[i][j] == 'w') continue;
if (map[i][j] == 'A' || map[i][j] == 'a') {
flag = 1;
}
if (i-1>=0 && dp[i-1][j]<dp[i][j]) {
dp[i][j] = dp[i-1][j] + 1;
}
if (j-1>=0 && dp[i][j-1]<dp[i][j]) {
dp[i][j] = dp[i][j-1] + 1;
}
if (map[i][j] == 'T' || map[i][j] == 't') {
dp[i][j]++;
}
}
}
}
int main() {
int n,m,time;
while (cin >> n >> m >> time) {
memset(map,0,sizeof(map));
setmap(map,n,m);
if (map[0][0]=='T'|| map[0][0]=='t'|| map[0][0]=='W'||map[0][0]
=='w' || map[n-1][m-1] == 'T' || map[n-1][m-1] == 't'
|| map[n-1][m-1] == 'W' || map[n-1][m-1] == 'w') {
cout << "Oh my god!" << endl;
}
else {
flag = 0;
//cout << map[0][0] << endl;
dfs(0,0,n,m,time);
if (dp[n-1][m-1] <= time && flag == 1) {
cout << dp[n-1][m-1] << endl;
}
else {
cout << "Oh my god!" << endl;
}
}
}
return 0;
}
