CPP教程-走迷宫

C++教程

走迷宫问题

题目描述

一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。

图例

. . ###
#. . . .
#. #. #
#. #. #
#. # . .

结题思路

使用广度优先搜索(扩散搜索并标记),并使用STL中的队列(也可以自己写)

代码分析

#include
using namespace std;
const int N=105;
int a[N][N],n,m,ans,d[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
queue >q;
void bfs()
{
    d[1][1]=1;a[1][1]=0;
    q.push(make_pair(1,1));
    while(q.size())
    {
        pair u=q.front();q.pop();
        if(u.first==n&&u.second==m)break;
        for(int i=0;i<4;i++)
        {
            int xx=u.first+dx[i],yy=u.second+dy[i];
            if(xx<1||xx>n||yy<1||yy>m||a[xx][yy]==0)continue;
            q.push(make_pair(xx,yy));
            d[xx][yy]=d[u.first][u.second]+1;
            a[xx][yy]=0;
        }
    }
    cout<>n>>m;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
      {
        char c;cin>>c;
        if(c=='.')a[i][j]=1;
      }
    bfs();
    return 0;
}

知识扩展

广度优先搜索

含义

使用类似递推的概念从一个点扩散到所有可扩散的点

图例

从左上角扩散到右下角,最少步数如下

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7