算法学习之BFS、DFS入门
0x1 问题描述
迷宫的最短路径
给定一个大小为N*M的迷宫。迷宫由通道和墙壁组成，每一步可以向相邻的上下左右四格的通道移动。请求出从起点到终点所需的最小步数。如果不能到达，输出“不能走到那里”。（N,M<=50,起点，终点分别用S,G表示）
输入样例：N=5,M=5
#S###
..##.
#.###
..###
..G##
1
2
3
4
5
6
输出：5
0x2 BFS解法
bfs用来求解最短路径相当简单。
#include <iostream>
#include <string.h>
#include <cstdio>
#include <queue>
#define maxsize 1000+7
using namespace std;
char maze[maxsize][maxsize];
int book[maxsize][maxsize];
int next[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int n,m;
int sx,sy,ex,ey;
typedef struct node
{
int x,y,step;
}Node;
void bfs()
{
queue <Node> q;
Node p;
p.x=sx;
p.y=sy;
p.step=0;
q.push(p);
book[sx][sy]=1;
while(!q.empty())
{
Node tmp=q.front();
q.pop();
if(tmp.x==ex&&tmp.y==ey)
{
cout<<tmp.step<<endl;
return;
}
for(int i=0;i<4;i++)
{
int nx=tmp.x+next[i][0];
int ny=tmp.y+next[i][1];
if(nx>=1&&ny>=1&&maze[nx][ny]!='#'&&!book[nx][ny])
{
book[nx][ny]=1;
Node tp;
tp.x=nx;
tp.y=ny;
tp.step=tmp.step+1;
q.push(tp);
}
}
}
cout<< -1 <<endl;
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
memset(book,0,sizeof(book));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>maze[i][j];
if(maze[i][j]=='S')
{
sx=i;
sy=j;
}
if(maze[i][j]=='G')
{
ex=i;
ey=j;
}
}
bfs();
}
return 0;
}
0x3 DFS解法
#include <iostream>
#include <string.h>
#include <cstdio>
#define maxsize 1000+7
using namespace std;
char mapplot[maxsize][maxsize];
int book[maxsize][maxsize];
int minstep=0x3f3f3f3f;
int sx,sy,ex,ey;
int n,m;
int dxy[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
void dfs(int x,int y, int step)
{
//cout<<x<<"-"<<y<<endl;
if(x<1||y<1||x>n||y>m)
return;
if(x==ex && y==ey)
{
if(step<minstep)
minstep=step;
return;
}
for(int i=0;i<4;i++)
{
int nx = x+dxy[i][0];
int ny = y+dxy[i][1];
//cout<<nx<<"-"<<ny<<endl;
if(mapplot[nx][ny]!='#' && book[nx][ny]==0)
{
book[nx][ny]=1;
dfs(nx,ny,step+1);
book[nx][ny]=0;
}
}
return;
}
int main()
{
memset(book,0,sizeof(book));
while(scanf("%d %d",&n, &m)!=EOF)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>mapplot[i][j];
if(mapplot[i][j]=='S')
{
sx=i;
sy=j;
}
if(mapplot[i][j]=='G')
{
ex=i;
ey=j;
}
}
//cout<< "sx:"<<sx<<"sy:"<<sy<<endl;
//cout<< "sx:"<<ex<<"sy:"<<ey<<endl;
dfs(sx,sy,0);
if(minstep!=0)
cout<< minstep <<endl;
else
cout<< -1 <<endl;
}
return 0;
}
0x4 总结
关于写这个模版的时候,我不是很注意标记,还有一些细节的地方,比如!='#' 因为dfs的进去的时候nx,ny为'G'
如果写的是=='.'就永远找不到目标点。