迷宫的最短路径

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

是道BFS的题目。

输入：

10 10

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

输出：

22


#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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 PA;

void bfs(){
    queue 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=0&&y_n>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;
}
图论

相关

图论---网络流

数的重心(图论深搜)

电子科技大学《图论及其应用》复习总结--第七章 图的着色

电子科技大学2017年《图论及其应用》试卷及答案

图论算法遍历基础

图论算法与模型（训练指南题库）

图论中的初始值

图论算法-最小生成树

LeetCode题解-07（简单图论）

图论学习笔记（二）

关于树（图论初步）

专题训练3-图论 - B - Learning Languages（并查集）

标签