POJ 3083 -- Children of the Candy Corn（DFS+BFS）

题意:

给定一个迷宫，S是起点，E是终点，#是墙不可走，.可以走

1）先输出左转优先时，从S到E的步数

2）再输出右转优先时，从S到E的步数

3）最后输出S到E的最短步数

 

解题思路：

前两问DFS，转向只要控制一下旋转方向就可以

首先设置前进方向对应的数字

向上——N——0

向右——E——1

向下——S——2

向左——W——3

比如说右转优先，即为向右，向前，向左，向后，即逆时针方向for(int i=1;i>=-2;i--)

左转优先，即为向左，向前，向右，向后，即顺时针方向for(int i=-1;i<=3;i++)

第三问最短路，BFS

普通递归（TLE）

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 using namespace std;  6 int r,c;///行r，列c  7 int r0,c0,r3,c3;///r0,c0用来标记入口，r3,c3用来标记出口  8 const char *dirs = "NESW";  9 const int maxn = 41; 10 char square[maxn][maxn]; 11 const int dr[] = {-1,0,1,0}; 12 const int dc[] = { 0,1,0,-1}; 13 struct node{ 14 int row,col,deep; 15 int dir;///0123对应NESW 16 node(int row=0,int col=0,int dir=0,int deep=0):row(row),col(col),dir(dir),deep(deep){} 17 }; 18 bool inside(int xx,int yy) 19 { 20     return xx>=1 && xx<=r && yy>=1 && yy<=c; 21 } 22  23 bool flag1; 24 int step1; 25 void dfs1(node *way,int x,int y,int d,int step) 26 {
   ///左转优先 27     way[step].row = x; 28     way[step].col = y; 29     way[step].dir = d; 30     if(x==r3 && y==c3)///走到出口 31     { 32         step1 = step; 33         flag1 = true; 34         return; 35     } 36     for(int i=-1;i<=3;i++) 37     { 38         int tempDir = (way[step].dir + 4 + i)%4;///进行旋转 39         int xx = way[step].row + dr[tempDir]; 40         int yy = way[step].col + dc[tempDir]; 41         if(inside(xx,yy) && square[xx][yy]!='#') 42         {
   ///没有出界，可以行走 43             dfs1(way,xx,yy,tempDir,step+1); 44         } 45         if(flag1) 46             return; 47     } 48     return; 49 } 50  51 int step2;bool flag2; 52 void dfs2(node *way,int x,int y,int d,int step) 53 {
   ///右转优先 54     way[step].row = x; 55     way[step].col = y; 56     way[step].dir = d; 57     if(x==r3 && y==c3)///走到出口 58     { 59         step2 = step; 60         flag2 = true; 61         return; 62     } 63     for(int i=1;i>=-2;i--) 64     { 65         int tempDir = (way[step].dir + 4 + i)%4;///进行旋转 66         int xx = way[step].row + dr[tempDir]; 67         int yy = way[step].col + dc[tempDir]; 68         if(inside(xx,yy) && square[xx][yy]!='#') 69         {
   ///没有出界，可以行走 70             dfs2(way,xx,yy,tempDir,step+1); 71         } 72         if(flag2) 73             return; 74     } 75     return; 76 } 77 node d[maxn][maxn][4]; 78  79 void bfs(int x,int y,int d) 80 { 81     queue
         
           q; 82     node u(x,y,d,1);///入口结点 83     q.push(u); 84     while(!q.empty()) 85     { 86         node u = q.front();q.pop(); 87         if(u.row == r3 && u.col == c3) 88         { 89             cout<
          
           <
           
            >n;117 while(n--)118 {119 cin>>c>>r;///输入为先输入列数，在输入行数120 char temp;121 for(int i=1;i<=r;i++)122 for(int j=1;j<=c;j++)123 {124 temp = getchar();125 while(temp == '\n') temp = getchar();126 square[i][j] = temp;127 if(temp == 'S'){r0 = i;c0 = j;}128 if(temp == 'E'){r3 = i;c3 = j;}129 }130 node *way = new node[maxn*maxn];131 ///求解左转优先132 flag1 = false;step1 = 1;133 int startdir = startDir();134 dfs1(way,r0,c0,startdir,1);135 if(flag1) cout<
            
             <<" ";136 ///求解右转优先137 flag2 = false;step2 = 1;138 dfs2(way,r0,c0,startdir,1);139 if(flag2) cout<
             
              <<" ";140 ///求解最短路径141 bfs(r0,c0,startdir);142 }143 return 0;144 }
             
            
           
          
         
        
       
      
     

 

 最终成功代码

Time Limit Exceeded原因：POJ对STL兼容性不高，使用queue超时

其次，DFS使用尾递归形式，遇到可行解，直接向下一层搜索

最后，BFS不能走重复路线，否则会陷入死循环，Runtime Error

仅此告诫自己

1 #include
     
        2 #include
      
         3 #include
       
          4 using namespace std;  5 int r,c;///行r，列c  6 int r0,c0,r3,c3;///r0,c0用来标记入口，r3,c3用来标记出口  7   8 const int maxn = 42;  9 char square[maxn][maxn]; 10 const int dr[] = {-1,0,1,0}; 11 const int dc[] = { 0,1,0,-1}; 12  13 struct node{ 14 int row,col,deep; 15 int dir;///0123对应NESW 16 node(int row=0,int col=0,int dir=0,int deep=0):row(row),col(col),dir(dir),deep(deep){} 17 }; 18 bool inside(int xx,int yy) 19 { 20     return xx>=1 && xx<=r && yy>=1 && yy<=c; 21 } 22 int dfs12(int x,int y,int d) 23 {
   ///左转优先 24     if(square[x][y] == 'E') 25         return 1; 26     int tempDir,xx,yy; 27     for(int i=-1;i<=3;i++) 28     { 29         tempDir = (d + 4 + i)%4;///进行旋转 30         xx = x + dr[tempDir]; 31         yy = y + dc[tempDir]; 32         if(inside(xx,yy) && square[xx][yy]!='#') 33         {
   ///没有出界，可以行走 34             break; 35         } 36     } 37     return dfs12(xx,yy,tempDir)+1; 38 } 39 int dfs22(int x,int y,int d) 40 {
   ///you转优先 41     if(square[x][y] == 'E') 42         return 1; 43     int tempDir,xx,yy; 44  45     for(int i=1;i>=-2;i--) 46     { 47         tempDir = (d + 4 + i)%4;///进行旋转 48         xx = x + dr[tempDir]; 49         yy = y + dc[tempDir]; 50         if(inside(xx,yy) && square[xx][yy]!='#') 51         {
   ///没有出界，可以行走 52             break; 53         } 54     } 55     return dfs22(xx,yy,tempDir)+1; 56 } 57  58 node queue[1600]; 59 bool has_walk[maxn][maxn]; 60 void bfs(int x,int y,int d) 61 { 62     int head=0,tail=1; 63     node u(x,y,d,1); 64     has_walk[x][y] = false; 65     queue[head] = u;///入口结点 66     while(head
        
         >n)101     while(n--)102     {103         cin>>c>>r;///输入为先输入列数，在输入行数104         memset(has_walk,true,sizeof(has_walk));///true表示当前格子没有走过，可以走105         char temp;106         for(int i=1;i<=r;i++)107             for(int j=1;j<=c;j++)108             {109                 temp = getchar();110                 while(temp == '\n') temp = getchar();111                 square[i][j] = temp;112                 if(temp == 'S'){r0 = i;c0 = j;}113                 if(temp == 'E'){r3 = i;c3 = j;}114             }115         ///求解左转优先116         int startdir = startDir();117         cout<
         
          <<" ";118         ///求解右转优先119         cout<
          
           <<" ";120 ///求解最短路径121 bfs(r0,c0,startdir);122 }123 return 0;124 }
          
         
        
       
      
     

 

最后给大家提供点测试样例：

58 8#########......##.####.##.####.##.####.##.####.##...#..##S#E####9 5##########.#.#.#.#S.......E#.#.#.#.##########8 5#########.#.#..#S......E#.#.#..#########2 3##SE##8 8######E##......##.####.##.####.##.####.##.####.##...#..##S######

结果：37 5 517 17 914 14 82 2 213 29 13