題目：

題目描述 Description
楚楚每一次都在你的幫助下過了一關(guān)又一關(guān)(比如他開宴會(huì))。這一次，你的才華讓楚楚被劫住了！(好心辦了壞事啊，下次不理他了==)
歹徒： hehe~
楚楚：(冷汗ing)干啥^^！(PS：現(xiàn)在還笑得出來?。。?
歹徒：搶劫的說~
楚楚：你們想干啥??！(PS：不是告訴你了，是搶劫~)
歹徒：這里是銀行的陷阱,也就是一個(gè)迷宮……你要帶我們離開這里……否則……
楚楚：(想：那你是咋抓到我的，郁悶)好吧……
楚楚認(rèn)為生命還是最重要的……(大不了出去以后找警察……)
于是，他認(rèn)命了……
他從歹徒口中得知這是一個(gè)方形的迷宮(歹徒老大：你還要啥形狀的，跟我說一聲！)，他們的位置是[1,1]，要走到[n,m],長(zhǎng)是n，寬是m，這是一個(gè)很大的迷宮，里面有陷阱(小明：能不能踩進(jìn)去的，說！楚楚：當(dāng)然不能，不過可以用輕功，多花一秒蓄力_{用輕功走過的陷阱會(huì)石化，變成路，而且剛好走過} 歹徒想：蝦米輕功_{明明是殺人利器}還好沒和他打起來_{)，還有墻(PS：說一聲，墻不能穿過，雖有輕功，但是還是過不去墻，這個(gè)墻也是銀行的秘密}即使你是神犇也不行哦~ 楚楚：又坑我~)。(小明：路呢？ 楚楚：廢話，當(dāng)然有，只不過這是銀行機(jī)密，不能說！)
楚楚想在最短時(shí)間里走出迷宮(小明：否則歹徒會(huì)發(fā)怒的，對(duì)不對(duì)？ 楚楚：廢話！)，若是超過了歹徒老大的忍耐時(shí)間time，那就……
(楚楚：小明……SOS，別忘了幫我報(bào)警！！ 傳呼機(jī)：嘀，嘀，嘀…… 楚楚：咋么可以這樣！可惡！)于是，他順便還要去找電話報(bào)個(gè)警(報(bào)警不需要時(shí)間，打通即可。且電話機(jī)可能有多個(gè)，但也沒有可能沒有~)。
楚楚：我的預(yù)感告訴我，這個(gè)迷宮只能向右或下走_郁悶了
輸入描述 Input Description
第1行是n,m, time，三個(gè)整數(shù)。
第2到n+1行每行有m個(gè)字母(有大寫也有小寫的)(楚楚：歹徒真笨_{，就不能翻譯一下嗎})。
字母解析：T(t)是陷阱，W(w)是墻，R(r)是路，A(a)是電話~ (遇到不認(rèn)識(shí)的字符就~算之為路！)
輸出描述 Output Description
僅一行走出迷宮的最小時(shí)間t(走一步要一秒的說)，不能在規(guī)定時(shí)間走出迷宮，或者打不了電話，請(qǐng)輸出“Oh my god!”(不包括引號(hào))。
樣例輸入 Sample Input
3 3 100
RRR
WWA
TRR
樣例輸出 Sample Output
4
數(shù)據(jù)范圍及提示 Data Size & Hint
時(shí)間限制**** Time Limitation
各個(gè)測(cè)試點(diǎn)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í)間~

此題是一道走迷宮的題，可以先判定第一個(gè)和最后一個(gè)的情況，如果不是路就死。
之后我們可以用一個(gè)數(shù)組表示到當(dāng)前為止共走了多少秒（此題只能向下或向右走），注意遇到陷阱可以走，但需要多加1s.
遇到電話就計(jì)數(shù)。
最后判定時(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;
}