迷宫的最短路径

本文主要是介绍迷宫的最短路径，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

迷宫的最短路径
给定一个大小为 NxM的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四格
的通道移动。请求出从起点到终点所需的最小步数。请注意，本题假定从起点一定可以移动
到终点。

是道BFS的题目。

输入：

10 10

#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#

输出：

22

#include <iostream>
#include<cstdlib>
#include<cstdio>
#include<stack>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<vector>
#include<map>
#include<set>
using namespace std;


char w[110][110];

int N=0;
int M=0;
int ans=0;

int s_x,s_y;
int d_x,d_y;

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

int mark[110][110];

typedef pair<int,int> PA;

void bfs(){
    queue<PA> q;
    q.push(PA(s_x,s_y));
    memset(mark, -1, sizeof(mark));
    mark[s_x][s_y]=0;
    while(q.size()){
        PA p=q.front();
        q.pop();
        if(p.first==d_x&&p.second==d_y){
            return;
        }
        for(int i=0;i<4;i++){
            int x_n=p.first+dx[i];
            int y_n=p.second+dy[i];
            
            if(w[x_n][y_n]!='#'&&x_n>=0&&x_n<N&&y_n>=0&&y_n<M&&mark[x_n][y_n]==-1){
                q.push(PA(x_n,y_n));
                mark[x_n][y_n]=mark[p.first][p.second]+1;
            }
            
            
    }
    }
}

int main()
{
    scanf("%d %d",&N,&M);
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            cin>>w[i][j];
            if(w[i][j]=='S'){
                s_x=i;
                s_y=j;
            }
            if(w[i][j]=='G'){
                d_x=i;
                d_y=j;
            }
        }
    }
    bfs();
    printf("%d\n",mark[d_x][d_y]);
    
   return 0;
}

这篇关于迷宫的最短路径的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！