求帮助 poj3083 Children of the Candy Corn 超时TLE，那位大神给帮忙看看怎么优化，帮帮我这个菜鸟

  1 ///2014.3.11 - 2014.3.13
  2 ///poj3083
  3 
  4 #include <iostream>
  5 #include <cstdio>
  6 using namespace std;
  7 
  8 int w,h;               ///记录迷宫的大小
  9 char maze[50][50];     ///记录迷宫
 10 int start_w,start_h;   ///记录迷宫的开始位置
 11 int start_pre;         ///其前一步的相对于现在位置的方向，
 12                             ///0表示在右，1表示在上面，2表示在左边，3是下面
 13 bool findmin;          ///标记有没有找到最短路
 14 int step;
 15 
 16 int next_w[4] = {1,0,-1,0};   ///方便走下一步
 17 int next_h[4] = {0,-1,0,1};
 18 
 19 void dfs(int h,int w,int pre,int l_r)
 20 {
 21     step++;
 22     if( maze[h][w]==‘E‘ ){
 23         return;
 24     }
 25     if( maze[h+next_h[(pre+l_r)%4] ][w+next_w[(pre+l_r)%4] ] !=‘#‘ ){
 26         dfs( h+next_h[(pre+l_r)%4], w+next_w[(pre+l_r)%4], (pre+l_r+2)%4,l_r);
 27     }
 28     else if( maze[h+next_h[(pre+l_r*2)%4] ][w+next_w[(pre+l_r*2)%4] ] !=‘#‘ ){
 29         dfs( h+next_h[(pre+l_r*2)%4], w+next_w[(pre+l_r*2)%4], (pre+l_r*2+2)%4,l_r);
 30     }
 31     else if( maze[h+next_h[(pre+l_r*3)%4] ][w+next_w[(pre+l_r*3)%4] ] !=‘#‘ ){
 32         dfs( h+next_h[(pre+l_r*3)%4], w+next_w[(pre+l_r*3)%4], (pre+l_r*3+2)%4,l_r);
 33     }
 34     else{
 35         dfs( h+next_h[pre], w+next_w[pre], (pre+2)%4,l_r);
 36     }
 37 }
 38 
 39 void bfs(int h,int w,int pre,int deep)
 40 {
 41     step++;
 42 
 43     if( findmin ) return;
 44     if( maze[h][w]==‘E‘ ){
 45         findmin = true;
 46         return;
 47     }
 48     if( deep==step ){
 49         return;
 50     }
 51 
 52     if( maze[h+next_h[(pre+1)%4] ][w+next_w[(pre+1)%4] ] !=‘#‘ ){
 53         bfs( h+next_h[(pre+1)%4], w+next_w[(pre+1)%4], (pre+1+2)%4,deep);
 54         step--;
 55     }
 56     if( maze[h+next_h[(pre+2)%4] ][w+next_w[(pre+2)%4] ] !=‘#‘ ){
 57         bfs( h+next_h[(pre+2)%4], w+next_w[(pre+2)%4], (pre+2+2)%4,deep);
 58         step--;
 59     }
 60     if( maze[h+next_h[(pre+3)%4] ][w+next_w[(pre+3)%4] ] !=‘#‘ ){
 61         bfs( h+next_h[(pre+3)%4], w+next_w[(pre+3)%4], (pre+3+2)%4,deep);
 62         step--;
 63     }
 64 }
 65 
 66 void init()
 67 {
 68     char c;
 69     scanf("%d%d",&w,&h);
 70     scanf("%c",&c);
 71     for(int i=1 ; i<=h ; i++){
 72         for(int j=1 ; j<=w ; j++){
 73             scanf("%c",&c);
 74             maze[i][j] = c;
 75             if( c==‘S‘ ){
 76                 start_w = j;
 77                 start_h = i;
 78                 if( j==1 )
 79                     start_pre = 2;
 80                 else if( j==w )
 81                     start_pre = 0;
 82                 else if( i==1 )
 83                     start_pre = 1;
 84                 else
 85                     start_pre = 3;
 86             }
 87         }
 88         scanf("%c",&c);
 89     }
 90     step = 0;
 91 }
 92 
 93 int main()
 94 {
 95 //    freopen("in","r",stdin);
 96 //    freopen("out","w",stdout);
 97 
 98     int cas;
 99     scanf("%d",&cas);
100     while( cas-- ){
101         init();
102 
103         dfs(start_h,start_w,start_pre,3);
104         printf("%d ",step);
105 
106         step = 0;
107         dfs(start_h,start_w,start_pre,1);
108         printf("%d ",step);
109 
110         findmin = false;
111         int deep;
112         for(deep=1 ; !findmin ; deep++){
113             step = 0;
114             bfs(start_h,start_w,start_pre,deep);
115         }
116         printf("%d\n",--deep);
117     }
118     return 0;
119 }