远程桌面登陆 自定义指令 string foreach 网络营销推广 io 在线考试系统代码 edate函数的使用方法 h5下拉刷新 字符串中包含某个字符串 webform开发教程 hadoop环境变量配置 kubernetes实战 range函数python python内置库 python中的index python中items python的extend python实战 python的安装路径 java如何连接mysql java安装步骤 java平台 linux服务器登录 php网络编程 lanhelper 图片链接生成器 联发科p70 sql行转列 ios删除描述文件 只狼全鬼佛 网红照片男 pr加速视频 目标聚光灯 cad2008汉化包 古特里克的杀生刀 祸星龙 怎么用打印机扫描文件 月之眼 鲁迅体
当前位置: 首页 > 学习教程  > 编程语言

啊哈算法之解救小哈

2020/8/11 19:43:43 文章标签:

题目描述
有一天,小哈一个去玩迷宫。但是方向感很不好的小哈很快就迷路了。小哼得知后便立即去解救无助的小哈。小哼当然是有备而来,已经弄清楚了迷宫地图,现在小哼要以最快速度去解救小哈。问题就此开始了…… 迷宫由n×m列的单元格组成,每个单元格要么是空地,要么是障碍物。你的任务是帮助小哼找到一条从迷宫的起点到小哈所在位置的最短路径,注意障碍物是不能走的,当然也不能走到迷宫之外。n,m≤100。
输入
第一行有两个数n 和m。n表示迷宫的行,m表示迷宫的列。接来下来n行m列为迷宫,0表示空地,1表示障碍物。最后一行4个数,前两个数为迷宫入口的x和y坐标。后两个为小哈的x和y坐标。
输出
一个整数表示小哼到小哈的最短步数。如果不能解救小哈则输出No Way!
样例输入

5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1 4 3
3 3
1 1 1 
0 1 0 
0 1 0 
2 1 3 3

样例输出

7
No Way!
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
struct node{
	int x;
	int y;
	int step;//记录所走的步数
}s,g,Node;
int n,m,flag;
int a[maxn][maxn];
int inq[maxn][maxn];
int X[5]={0,0,0,1,-1};
int Y[5]={0,1,-1,0,0};
bool judge(int x,int y){
	if(x<1||x>n||y<1||y>m)return false;
	if(a[x][y]==1||inq[x][y]==true)return false;
	return true;
}
void bfs(){//宽度优先搜索
	queue<node>q;
	q.push(s);
	while(q.empty()!=1){
		node top=q.front();
		q.pop();
		if(top.x==g.x&&top.y==g.y){
			flag=1;
			cout<<top.step<<endl;
			return;
		}
		for(int i=1;i<=4;i++){
			int newx=top.x+X[i];
			int newy=top.y+Y[i];
			if(judge(newx,newy)){
				Node.x=newx,Node.y=newy;
				Node.step=top.step+1;
				q.push(Node);
				inq[newx][newy]=true;
			}
		}
	}
	if(flag==0){
		cout<<"No Way!"<<endl;
		return;
	}
}
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(cin>>n>>m){
    	flag=0;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			cin>>a[i][j];
    			inq[i][j]=false;
			}
		}
		cin>>s.x>>s.y>>g.x>>g.y;
		s.step=0;
		bfs();
	}
	
    return 0;
}

本文链接: http://www.dtmao.cc/news_show_100166.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?