codevs1337 银行里的迷宫

题目：

题目描述 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
数据范围及提示 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上，所以走这一块不用时间~

此题是一道走迷宫的题，可以先判定第一个和最后一个的情况，如果不是路就死。
之后我们可以用一个数组表示到当前为止共走了多少秒（此题只能向下或向右走），注意遇到陷阱可以走，但需要多加1s.
遇到电话就计数。
最后判定时间和有无电话即可。

参考代码：

#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;
}