算法学习之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'

如果写的是=='.'就永远找不到目标点。