【原创】转载请注明出处 【浙江大学 程序设计专题】
【地图求解器】
本题目要求输入一个迷宫地图，输出从起点到终点的路线。
基本思路是从起点(Sx,Sy)每次枚举该格子上下左右四个方向，直到走到终点(Tx,Ty)。
方法一：如果使用递归方法，则可以使用深度优先搜索算法，但此方法不能保证答案步数最优。
方法二： 如果要求答案步数最少，则使用广度优先搜索算法，但此方法通常不使用递归函数实现。
DFS版代码
#include <stdio.h>
#include <string.h> /*Header which contains the output function*/
#include "prnt_route.h" int n,m;
int visited[][];
struct PII from[][];
/*Save the route.*/ const int dx[]={-,,,},dy[]={,,,-}; char Map[][]; int Dfs(const int Sx,const int Sy, const int Tx,const int Ty)
{
if(Sx==Tx && Sy==Ty) return ;
int i;
for(i=;i<;++i)/*Search four directions*/
{
int tx=Sx+dx[i],ty=Sy+dy[i];/*tx,ty refers to the next grid.*/
if(tx>= && ty>= && tx<n && ty<m &&
!visited[tx][ty] && Map[tx][ty]!='#')
/*check if (tx,ty) is reachable*/
{
visited[tx][ty]=;
if(Dfs(tx,ty,Tx,Ty))
{
/*Route is found.*/
from[tx][ty]=make_pair(Sx,Sy);
return ;
}
}
}
return ;
} int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
int i,j,Sx,Sy,Tx,Ty;
scanf("%d%d",&n,&m);
Sx=Sy=,Tx=n-,Ty=m-;
for(i=;i<n;++i) scanf("%s",Map[i]); /*Find the starting and ending points.*/
for(i=;i<n;++i)
for(j=;j<m;++j)
if(Map[i][j]=='S') Sx=i,Sy=j;
else if(Map[i][j]=='T') Tx=i,Ty=j; /*Dfs will return 1 if a solution is found, 0 otherwise.*/
if(Dfs(Sx,Sy,Tx,Ty)) Print_Ans(Sx,Sy,Tx,Ty);
else printf("No Solution.\n");
return ;
}
BFS版代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h> /*Header contains the outout function*/
#include "prnt_route.h" int n,m;
int visited[][];
struct PII from[][];
/*Save the route*/ char Map[][]; int Bfs(const int Sx,const int Sy, const int Tx,const int Ty)
{
struct PII Q[(n+)*(m+)];/*Queue for Bfs*/
int front=,back=;/*head and tail pointer of the queue*/
memset(visited,,sizeof(visited));
memset(from,,sizeof(from));
Q[back++]=make_pair(Sx,Sy);/*push the starting point*/
visited[Sx][Sy]=;
while(front!=back && !visited[Tx][Ty])
{
struct PII t=Q[front++];/*Pop out*/
/*Search four directions*/
if(t.x> && !visited[t.x-][t.y] && Map[t.x-][t.y]!='#')/*up*/
{
Q[back++]=make_pair(t.x-,t.y);/*push*/
visited[t.x-][t.y]=;
from[t.x-][t.y]=make_pair(t.x,t.y);
}
if(t.x<n- && !visited[t.x+][t.y] && Map[t.x+][t.y]!='#')/*down*/
{
Q[back++]=make_pair(t.x+,t.y);/*push*/
visited[t.x+][t.y]=;
from[t.x+][t.y]=make_pair(t.x,t.y);
}
if(t.y> && !visited[t.x][t.y-] && Map[t.x][t.y-]!='#')/*left*/
{
Q[back++]=make_pair(t.x,t.y-);/*push*/
visited[t.x][t.y-]=;
from[t.x][t.y-]=make_pair(t.x,t.y);
}
if(t.y<m- && !visited[t.x][t.y+] && Map[t.x][t.y+]!='#')/*right*/
{
Q[back++]=make_pair(t.x,t.y+);/*push*/
visited[t.x][t.y+]=;
from[t.x][t.y+]=make_pair(t.x,t.y);
}
}
return visited[Tx][Ty];
} int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
int i,j,Sx,Sy,Tx,Ty;
scanf("%d%d",&n,&m);
Sx=Sy=,Tx=n-,Ty=m-;
for(i=;i<n;++i) scanf("%s",Map[i]); /*Find the starting and ending points*/
for(i=;i<n;++i)
for(j=;j<m;++j)
if(Map[i][j]=='S') Sx=i,Sy=j;
else if(Map[i][j]=='T') Tx=i,Ty=j; /*Bfs will return 1 if route is found.*/
if(Bfs(Sx,Sy,Tx,Ty)) Print_Ans(Sx,Sy,Tx,Ty);
else printf("No Solution.\n");
return ;
}
print_route.h(两篇代码公用)
/*Output function*/
#include <stdio.h>
struct PII { int x,y; };/*coordinate container*/
struct PII make_pair(const int x,const int y)
{ struct PII t; t.x=x,t.y=y; return t; }
extern int n,m;
extern int visited[][];
extern struct PII from[][];
extern char Map[][];
void Print_Ans(const int Sx,const int Sy,const int Tx,const int Ty)
{
int x=Tx,y=Ty,dir=,td,i,j,tempx,tempy;
/*'dir' is the current direction, while 'td' is the last direcion.*/
while(x!=Sx || y!=Sy)
{
/*judge the direction*/
if(from[x][y].y==y && from[x][y].x==x+) Map[x][y]='^',td=;
if(from[x][y].y==y && from[x][y].x==x-) Map[x][y]='V',td=;
if(from[x][y].x==x && from[x][y].y==y+) Map[x][y]='<',td=;
if(from[x][y].x==x && from[x][y].y==y-) Map[x][y]='>',td=;
/*decide which conner character should be output.*/
if(dir== && td==) Map[x][y]='}';
if(dir== && td==) Map[x][y]='}';
if(dir== && td==) Map[x][y]='{';
if(dir== && td==) Map[x][y]='{';
if(dir== && td==) Map[x][y]=']';
if(dir== && td==) Map[x][y]=']';
if(dir== && td==) Map[x][y]='[';
if(dir== && td==) Map[x][y]='[';
tempx=x,tempy=y; dir=td;
x=from[tempx][tempy].x;
y=from[tempx][tempy].y;
}
Map[Sx][Sy]='S';
Map[Tx][Ty]='T';
for(i=;i<n;++i)
{
for(j=;j<m;++j)
{
/*output with special chars.*/
if(Map[i][j]=='#') printf("█");
else if(Map[i][j]=='.') printf(" ");
else if(Map[i][j]=='^') printf("↑");
else if(Map[i][j]=='V') printf("↓");
else if(Map[i][j]=='<') printf("←");
else if(Map[i][j]=='>') printf("→");
else if(Map[i][j]=='+') printf("╋");
else if(Map[i][j]=='[') printf("┏");
else if(Map[i][j]==']') printf("┓");
else if(Map[i][j]=='{') printf("┗");
else if(Map[i][j]=='}') printf("┛");
else printf("☆");
}
printf("\n");
}
return ;
}
标准ascii字符版print_route.h
#include <stdio.h>
struct PII { int x,y; };
struct PII make_pair(const int x,const int y)
{ struct PII t; t.x=x,t.y=y; return t; }
extern int n,m;
extern int visited[][];
extern struct PII from[][];
extern char Map[][];
void Print_Ans(const int Sx,const int Sy,const int Tx,const int Ty)
{
int x=Tx,y=Ty,dir=,td,i,tempx,tempy;
while(x!=Sx || y!=Sy)
{
if(from[x][y].y==y && from[x][y].x==x+) Map[x][y]='|',td=;
if(from[x][y].y==y && from[x][y].x==x-) Map[x][y]='|',td=;
if(from[x][y].x==x && from[x][y].y==y+) Map[x][y]='-',td=;
if(from[x][y].x==x && from[x][y].y==y-) Map[x][y]='-',td=;
if(dir== && td==) Map[x][y]='+';
if(dir== && td==) Map[x][y]='+';
if(dir== && td==) Map[x][y]='+';
if(dir== && td==) Map[x][y]='+';
if(dir== && td==) Map[x][y]='+';
if(dir== && td==) Map[x][y]='+';
if(dir== && td==) Map[x][y]='+';
if(dir== && td==) Map[x][y]='+';
tempx=x,tempy=y; dir=td;
x=from[tempx][tempy].x;
y=from[tempx][tempy].y;
}
Map[Sx][Sy]='S';
Map[Tx][Ty]='T';
for(i=;i<n;++i)printf("%s\n",Map[i]);
return ;
}
【地图生成器】
方法，使用DFS，每次随机一个方向进行扩展。但这样可能导致一条路径过长，岔路过短。
所以加入三个参数：
1.搜索过程中有一定几率保持上一次的方向，称为RATE_KEEP_DIR
2.搜索过程中有一定几率停止当前道路的搜索，直接return，这个参数称为RETURN_RATE
3.每条链有一个最大长度，称为TWIST_RATE
通过修改这三个参数，可以改变地图的性态。
生成器代码使用C++，编译需要加-std=c++11参数，代码如下
//Compile with -std=c++11
#include <bits/stdc++.h> using namespace std; const int RATE_KEEP_DIR=;
const int TWIST_RATE=;
const int RETURN_RATE=; int n,m,Sx,Sy,Tx,Ty,Max;
char Map[][];
typedef pair<int,int> PII;
const int dx[]={-,,,},dy[]={,,,-};
const int Dx[]={-,,,},Dy[]={,,,-}; mt19937 RND(time()); //Check if (x,y) has a neighbour can go.
bool Check(const int x,const int y)
{
for(int i=;i<;++i)
{
int nx=x+dx[i],ny=y+dy[i],Nx=x+Dx[i],Ny=y+Dy[i];
if(Nx>= && Nx<n && Ny>= && Ny<m && (Map[Nx][Ny]=='#' && Map[nx][ny]=='#'))return true;
} return false;
} void Dfs(const int x,const int y,const int depth,int Lim,const int last_dir)
{
if(depth>Max)Tx=x,Ty=y,Max=depth;//find a longest route
if(depth>Lim) return ;
Map[x][y]='.';
while(Check(x,y))
{
int t=RND()%;//random direction
if(RND()%<RATE_KEEP_DIR) t=last_dir;//chance of keeping direction.
int nx=x+dx[t],ny=y+dy[t],Nx=x+Dx[t],Ny=y+Dy[t];
if(nx< || nx>n- || ny< || ny>m- || Map[nx][ny]!='#')continue;
if(Nx< || Nx>n- || Ny< || Ny>m- || Map[Nx][Ny]!='#')continue;
if(Nx== || Nx==n- || Ny== || Ny==m-) { Map[nx][ny]='.'; continue; }
Map[nx][ny]='.'; Map[Nx][Ny]='.';
Dfs(Nx,Ny,depth+,Lim,t); //chance of returning directly, without expanding, for more branch roads
if((int)(RND()%)<(min(n,m)<?:RETURN_RATE)) return ; Lim=depth+max(min(n,m)/TWIST_RATE,);
}
return ;
} int main()
{
freopen("in.txt","w",stdout);
scanf("%d%d",&n,&m);
printf("%d %d\n",n,m);
for(int i=;i<n;++i) for(int j=;j<m;++j) Map[i][j]='#';
Sx=Sy=;
// the length limit of each branch road.
Dfs(Sx,Sy,,max(min(n,m)/TWIST_RATE,),);
//set starting and ending points.
Map[Sx][Sy]='S';
Map[Tx][Ty]='T';
for(int i=;i<n;++i) printf("%s\n",Map[i]);
return ;
}
以下C++代码可以将生成器生成的地图转化为全角符号，便于查看
#include <bits/stdc++.h> int n,m;
char Map[][]; using namespace std; int main()
{
freopen("in.txt","r",stdin);
freopen("view.txt","w",stdout);
scanf("%d%d",&n,&m);
for(int i=;i<n;++i)
scanf("%s",Map[i]);
for(int i=;i<n;++i)
{
for(int j=;j<m;++j)
{
if(Map[i][j]=='#') printf("█");
else if(Map[i][j]=='.') printf(" ");
else printf("☆");
}
printf("\n");
}
return ;
}