经典迷宫最短路问题_java迷宫最短路-程序员宅基地

’#‘是墙，’S‘起点，’G‘终点，’.‘可走

input

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

output

#include <cstdio>
#include <utility>
#include <queue>
#include <cstring>
#define maxn 505
using namespace std;
const int INF = 10000000;
typedef pair<int,int> PA; 

//输入
char maze[maxn][maxn+1];	//迷宫字符串 
int n,m;				//行列 
int sx,sy;				//起点 
int gx,gy; 				//终点 

int d[maxn][maxn];		//到各个位置的最短距离数组

//4个方向移动的向量
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

//求从{sx,sy}到{gx,gy}的最短距离
//如果无法到达，则是INF
int bfs(){
	queue<PA> que;
	//memset(d,INF,sizeof(d));			//位置初始化为INF
	//不能用memset 
	 for (int i = 0; i < n; i++) 
    	for (int j = 0; j <m; j++) d[i][j] = INF;
	
	//将起点加入队列 ，并将这一地点的距离设置为0 
	que.push(PA(sx,sy));
	d[sx][sy]=0;
	
	//不断循环直到队列的长度为0
	while(que.size()){
		PA p=que.front();
		que.pop();
		//如果取出的状态已经是终点，则结束搜索
		if(p.first==gx&&p.second==gy) break; 
		
		//四个方向循环
		for(int i=0;i<4;i++){
			//移动之后的位置为(nx,ny)
			int nx=p.first+dx[i];
			int ny=p.second+dy[i];		
			
			//判断是否可以移动以及是否已经访问过（d=INF访问过） 
			if(nx>=0&&nx<n&&ny>=0&&ny<m&&maze[nx][ny]!='#'&&d[nx][ny]==INF){
				//可以移动的话加入到队列，并且到该位置的距离确定为到p的距离+1
				que.push(PA(nx,ny));
				d[nx][ny]=d[p.first][p.second]+1; 
			} 
		}
	}
	return d[gx][gy];	
} 
 
int main(){
	freopen("migong.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%s",maze[i]);
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++)
			if(maze[i][j]=='S'){
				sx=i,sy=j;
			}
			else if(maze[i][j]=='G'){
				gx=i;gy=j;
			}
	}
	printf("%d\n",bfs());
}

本文链接：https://blog.csdn.net/sinat_19628145/article/details/51089866

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

源代码图纸文档防泄密场景方案分析-程序员宅基地

文章浏览阅读161次，点赞5次，收藏3次。财务数据、员工信息、工资信息、客户和业务数据等被员工非法获取、外泄

Linux查磁盘大小命令,linux系统查看磁盘空间的命令是什么-程序员宅基地

文章浏览阅读2k次。linux系统查看磁盘空间的命令是【df -hl】，该命令可以查看磁盘剩余空间大小。如果要查看每个根路径的分区大小，可以使用【df -h】命令。df命令以磁盘分区为单位查看文件系统。本文操作环境：red hat enterprise linux 6.1系统、thinkpad t480电脑。(学习视频分享：linux视频教程)Linux 查看磁盘空间可以使用 df 和 du 命令。df命令df 以磁..._df -hl

Office & delphi_range[char(96 + acolumn) + inttostr(65536)].end[xl-程序员宅基地

文章浏览阅读923次。uses ComObj;var ExcelApp: OleVariant;implementationprocedure TForm1.Button1Click(Sender: TObject);const // SheetType xlChart = -4109; xlWorksheet = -4167; // WBATemplate xlWBATWorksheet = -4167_range[char(96 + acolumn) + inttostr(65536)].end[xlup]

若依 quartz 定时任务中 service mapper无法注入解决办法_ruoyi-quartz无法引入ruoyi-admin的service-程序员宅基地

文章浏览阅读2.3k次。上图为任务代码，在任务具体执行的方法中使用，一定要写在方法内使用SpringContextUtil.getBean()方法实例化Spring service类下边是ruoyi-quartz模块中util/SpringContextUtil.java(已改写)import org.springframework.beans.BeansException;import org.springframework.context.ApplicationContext;import org.s..._ruoyi-quartz无法引入ruoyi-admin的service

CentOS7配置yum源-程序员宅基地

文章浏览阅读2w次，点赞10次，收藏77次。yum，全称“Yellow dog Updater, Modified”，是一个专门为了解决包的依赖关系而存在的软件包管理器。可以这么说，yum 是改进型的 RPM 软件管理器，它很好的解决了 RPM 所面临的软件包依赖问题。yum 在服务器端存有所有的 RPM 包，并将各个包之间的依赖关系记录在文件中，当管理员使用 yum 安装 RPM 包时，yum 会先从服务器端下载包的依赖性文件，通过分析此文件从服务器端一次性下载所有相关的 RPM 包并进行安装。_centos7配置yum源