专栏首页ypw迷宫的最短路径

迷宫的最短路径

题意:给定一个大小为N * M的迷宫,迷宫由通道与墙壁组成,每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需要的最下步数。

思路:很明显是BFS问题,我们从起点出发,然后把步数为1的点全部遍历,然后是扩展到步数为2的全部的点,然后是步数为3的…直到出现了终点,此时我们所求的步数即为最短路。

#include<bits/stdc++.h>
#define maxn 100004
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int> p;
int sx,sy;
int gs,gy;
char a[maxn][maxn];
int  dis[maxn][maxn];
int dx={1,0,-1,0};
int dy={0,1,0,-1};


int bfs(){
	queue<p> que;
		for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
	    dis[i][j] = inf;
		}
	}
		que.push(p(sx,sy));
		d[sx][sy] = 0;
		
		while(que.size()){
			p  = que.front();que.pop();
			if(p.first == gx && p.second == gy) break;
			
			for(int i=0;i<4;i++){
				int nx = p.first + dx[i],ny = p.second + dy[i];
				
				if(nx>=1 && nx<=n && ny>=1 && ny<=m && a[nx][ny]!='#' && dis[nx][ny]==inf){
					que.push(p(nx,ny));
					dis[nx][ny] = dis[p.first][p.second] + 1; 
				}
 			}
		}
		return dis[gx][gy];
	
}
void solve(){
	int res = bfs();
	cout<<res<<endl;
}


int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j] == 'S'){
				sx = i;
				sy = j;
			}
			if(a[i][j] == 'G'){
				gs = i;
				gy = j;
			}
		}
	}
	
	solve();
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 口算训练 HDU - 6287

    小Q非常喜欢数学,但是他的口算能力非常弱。因此他找到了小T,给了小T一个长度为n的正整数序列a1,a2,…,an,要求小T抛出m个问题以训练他的口算能力。

    用户7727433
  • 回溯法求组合问题

    用户7727433
  • 用归并排序求逆序对数(包括归并排序算法实现及代码)

    那么我们很容易想到这个题有一种O(n*n)的暴力解法,但这不是我们所需要的,所以,要想归并排序来实现求逆序对数,那么首先我们要了解并掌握归并排序算法。

    用户7727433
  • 一遍记住Java常用的八种排序算法

    (如果每次比较都交换,那么就是交换排序;如果每次比较完一个循环再交换,就是简单选择排序。)

    Java旅途
  • 集合中随机取不重复的索引

    有时候希望从一个集合中随机取n个元素不重复 那么就取到这n个数字的索引 public static int[] GetRandomArray(int Numb...

    用户1055830
  • nyoj 115------城市平乱( dijkstra // bellman )

    城市平乱 时间限制:1000 ms  |  内存限制:65535 KB 难度:4 描述 南将军统领着N个部队,这N个部队分别驻扎在N个不同的城市。 他在用这N个...

    Gxjun
  • Flyod 算法(两两之间的最短路径)

    Flyod 算法(两两之间的最短路径) 动态规划方法,通过相邻矩阵, 然后把最后的结果存在这么一个矩阵里面,(i,j), #include <iostream...

    Gxjun
  • 第7章 套接字选项

    这一章是一个无比巨大的巨坑!!! 套接字选项相关函数: #include <sys/socket.h> int getsockopt(int sock, i...

    _gongluck
  • 并查集(个人模版)

    并查集: 1 int find(int a) 2 { 3 int r=a; 4 while(f[r]!=r) 5 ...

    Angel_Kitty
  • 2017广东工业大学程序设计竞赛决赛 题解&源码(A,数学解方程,B,贪心博弈,C,递归,D,水,E,贪心,面试题,F,贪心,枚举,LCA,G,dp,记忆化搜索,H,思维题)

    心得: 这比赛真的是不要不要的,pending了一下午,也不知道对错,直接做过去就是了,也没有管太多! Problem A: 两只老虎 Description ...

    Angel_Kitty

扫码关注云+社区

领取腾讯云代金券