【原创】转载请注明出处 【浙江大学 程序设计专题】

【地图求解器】

本题目要求输入一个迷宫地图，输出从起点到终点的路线。

基本思路是从起点(Sx,Sy)每次枚举该格子上下左右四个方向，直到走到终点(Tx,Ty)。

方法一：如果使用递归方法，则可以使用深度优先搜索算法，但此方法不能保证答案步数最优。

方法二： 如果要求答案步数最少，则使用广度优先搜索算法，但此方法通常不使用递归函数实现。

DFS版代码

1 #include 
      
        2 #include 
       
         3  4 /*Header which contains the output function*/ 5 #include "prnt_route.h" 6  7 int    n,m; 8 int    visited[1100][1100]; 9 struct PII    from[1100][1100];10 /*Save the route.*/11 12 const int dx[4]={-1,0,1,0},dy[4]={
    0,1,0,-1};13 14 char    Map[1100][1100];15 16 int    Dfs(const int Sx,const int Sy, const int Tx,const int Ty)17 {18     if(Sx==Tx && Sy==Ty) return 1;19     int i;20     for(i=0;i<4;++i)/*Search four directions*/21     {22         int tx=Sx+dx[i],ty=Sy+dy[i];/*tx,ty refers to the next grid.*/23         if(tx>=0 && ty>=0 && tx
       
      

BFS版代码

1 #include 
      
        2 #include 
       
         3 #include 
        
          4  5 /*Header contains the outout function*/ 6 #include "prnt_route.h" 7  8 int n,m; 9 int visited[1100][1100];10 struct PII  from[1100][1100];11 /*Save the route*/12 13 char    Map[1100][1100];14 15 int Bfs(const int Sx,const int Sy, const int Tx,const int Ty)16 {17     struct PII Q[(n+5)*(m+5)];/*Queue for Bfs*/18     int front=0,back=0;/*head and tail pointer of the queue*/19     memset(visited,0,sizeof(visited));20     memset(from,0,sizeof(from));21     Q[back++]=make_pair(Sx,Sy);/*push the starting point*/ 22     visited[Sx][Sy]=1;23     while(front!=back && !visited[Tx][Ty])24     {25         struct PII t=Q[front++];/*Pop out*/26         /*Search four directions*/27         if(t.x>0 && !visited[t.x-1][t.y] && Map[t.x-1][t.y]!='#')/*up*/28         {29             Q[back++]=make_pair(t.x-1,t.y);/*push*/30             visited[t.x-1][t.y]=1;31             from[t.x-1][t.y]=make_pair(t.x,t.y);32         }33         if(t.x
         
          0 && !visited[t.x][t.y-1] && Map[t.x][t.y-1]!='#')/*left*/40         {41             Q[back++]=make_pair(t.x,t.y-1);/*push*/42             visited[t.x][t.y-1]=1;43             from[t.x][t.y-1]=make_pair(t.x,t.y);44         }45         if(t.y
         
        
       
      

print_route.h(两篇代码公用)

1 /*Output function*/ 2  3 #include 
      
        4  5 struct PII { int x,y; };/*coordinate container*/ 6 struct PII make_pair(const int x,const int y) 7 { struct PII t; t.x=x,t.y=y; return t; } 8  9 extern int    n,m;10 extern int    visited[1100][1100];11 extern struct PII    from[1100][1100];12 13 extern char    Map[1100][1100];14 15 void    Print_Ans(const int Sx,const int Sy,const int Tx,const int Ty)16 {17     int x=Tx,y=Ty,dir=0,td,i,j,tempx,tempy;18     /*'dir' is the current direction, while 'td' is the last direcion.*/19     while(x!=Sx || y!=Sy)20     {21         /*judge the direction*/22         if(from[x][y].y==y && from[x][y].x==x+1) Map[x][y]='^',td=0;23         if(from[x][y].y==y && from[x][y].x==x-1) Map[x][y]='V',td=1;24         if(from[x][y].x==x && from[x][y].y==y+1) Map[x][y]='<',td=2;25         if(from[x][y].x==x && from[x][y].y==y-1) Map[x][y]='>',td=3;26         /*decide which conner character should be output.*/27         if(dir==0 && td==3) Map[x][y]='}';28         if(dir==2 && td==1) Map[x][y]='}';29         if(dir==3 && td==1) Map[x][y]='{
     ';30         if(dir==0 && td==2) Map[x][y]='{
     ';31         if(dir==1 && td==3) Map[x][y]=']';32         if(dir==2 && td==0) Map[x][y]=']';33         if(dir==3 && td==0) Map[x][y]='[';34         if(dir==1 && td==2) Map[x][y]='[';35         tempx=x,tempy=y; dir=td;36         x=from[tempx][tempy].x;37         y=from[tempx][tempy].y;38     }39     Map[Sx][Sy]='S';40     Map[Tx][Ty]='T';41 42     for(i=0;i
       
        ') printf("→");53             else if(Map[i][j]=='+') printf("╋");54             else if(Map[i][j]=='[') printf("┏");55             else if(Map[i][j]==']') printf("┓");56             else if(Map[i][j]=='{
     ') printf("┗");57             else if(Map[i][j]=='}') printf("┛");58             else printf("☆");59         }60         printf("\n");61     }62     return ;63 }
       
      

标准ascii字符版print_route.h

1 #include 
      
        2  3 struct PII { int x,y; }; 4 struct PII make_pair(const int x,const int y) 5 { struct PII t; t.x=x,t.y=y; return t; } 6  7 extern int    n,m; 8 extern int    visited[1100][1100]; 9 extern struct PII    from[1100][1100];10 11 extern char    Map[1100][1100];12 13 void    Print_Ans(const int Sx,const int Sy,const int Tx,const int Ty)14 {15     int x=Tx,y=Ty,dir=0,td,i,tempx,tempy;16     while(x!=Sx || y!=Sy)17     {18         if(from[x][y].y==y && from[x][y].x==x+1) Map[x][y]='|',td=0;19         if(from[x][y].y==y && from[x][y].x==x-1) Map[x][y]='|',td=1;20         if(from[x][y].x==x && from[x][y].y==y+1) Map[x][y]='-',td=2;21         if(from[x][y].x==x && from[x][y].y==y-1) Map[x][y]='-',td=3;22         if(dir==0 && td==3) Map[x][y]='+';23         if(dir==2 && td==1) Map[x][y]='+';24         if(dir==3 && td==1) Map[x][y]='+';25         if(dir==0 && td==2) Map[x][y]='+';26         if(dir==1 && td==3) Map[x][y]='+';27         if(dir==2 && td==0) Map[x][y]='+';28         if(dir==3 && td==0) Map[x][y]='+';29         if(dir==1 && td==2) Map[x][y]='+';30         tempx=x,tempy=y; dir=td;31         x=from[tempx][tempy].x;32         y=from[tempx][tempy].y;33     }34     Map[Sx][Sy]='S';35     Map[Tx][Ty]='T';36 37     for(i=0;i
      

 

【地图生成器】

方法，使用DFS，每次随机一个方向进行扩展。但这样可能导致一条路径过长，岔路过短。

所以加入三个参数：

　　1.搜索过程中有一定几率保持上一次的方向，称为RATE_KEEP_DIR

　　2.搜索过程中有一定几率停止当前道路的搜索，直接return，这个参数称为RETURN_RATE

　　3.每条链有一个最大长度，称为TWIST_RATE

通过修改这三个参数，可以改变地图的性态。

 

生成器代码使用C++，编译需要加-std=c++11参数，代码如下

1 //Compile with -std=c++11 2 #include 
      
        3  4 using namespace std; 5  6 const int RATE_KEEP_DIR=000; 7 const int TWIST_RATE=10; 8 const int RETURN_RATE=100; 9 10 int n,m,Sx,Sy,Tx,Ty,Max;11 char    Map[1100][1100];12 typedef pair
       
           PII;13 const int dx[4]={-1,0,1,0},dy[4]={
    0,1,0,-1};14 const int Dx[4]={-2,0,2,0},Dy[4]={
    0,2,0,-2};15 16 mt19937     RND(time(0));17 18 //Check if (x,y) has a neighbour can go. 19 bool    Check(const int x,const int y)20 {21     for(int i=0;i<4;++i)22     {23         int nx=x+dx[i],ny=y+dy[i],Nx=x+Dx[i],Ny=y+Dy[i];24         if(Nx>=0 && Nx
        
         =0 && Ny
         
          Max)Tx=x,Ty=y,Max=depth;//find a longest route31     if(depth>Lim) return ;32     Map[x][y]='.';33     while(Check(x,y))34     {35         int t=RND()%4;//random direction36         if(RND()%1000
          
           n-1 || ny<0 || ny>m-1 || Map[nx][ny]!='#')continue;39         if(Nx<0 || Nx>n-1 || Ny<0 || Ny>m-1 || Map[Nx][Ny]!='#')continue;40         if(Nx==0 || Nx==n-1 || Ny==0 || Ny==m-1) { Map[nx][ny]='.'; continue; }41         Map[nx][ny]='.'; Map[Nx][Ny]='.';42         Dfs(Nx,Ny,depth+1,Lim,t);43         44         //chance of returning directly, without expanding, for more branch roads 45         if((int)(RND()%1000)<(min(n,m)<100?0:RETURN_RATE)) return ;46         47         Lim=depth+max(min(n,m)/TWIST_RATE,5);48     }49     return ;50 }51 52 int main()53 {54     freopen("in.txt","w",stdout);55     scanf("%d%d",&n,&m);56     printf("%d %d\n",n,m);57     for(int i=0;i
          
         
        
       
      

以下C++代码可以将生成器生成的地图转化为全角符号，便于查看

1 #include 
      
        2  3 int n,m; 4 char    Map[1100][1100]; 5  6 using namespace std; 7  8 int main() 9 {10     freopen("in.txt","r",stdin);11     freopen("view.txt","w",stdout);12     scanf("%d%d",&n,&m);13     for(int i=0;i