走迷宫(二):在XX限制条件下,是否走得出
2024-08-27 20:12:21
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1728
解题方法:BFS+访问数组vis[][];
给你起点位置和终点位置,让你判断能不能到达,并且拐弯数不能超过某个值。
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std; //int dx[]={0,0,-1,1};
//int dy[]={1,-1,0,0};
int dir[][] = { , , -, , , , , - };
char map[][];
int vis[][];
int m,n;
int k; struct point
{
int x;
int y;
int kk;
}; void bfs(point s,point u)
{
int flag=;
point q,p;
s.kk=-; //(新增)-1,不是0 vis[s.x][s.y]=; //(新增)访问的标志 queue<point>tp;
tp.push(s); while(!tp.empty ())
{
q=tp.front();
tp.pop(); if(q.x==u.x&&q.y==u.y&&q.kk<=k) //(新增)q.kk<=k
{
flag=;
break;
} int i;
p.kk=q.kk+; //(新增)
for(i=;i<;i++)
{
p.x=q.x+dir[i][];//p.x=q.x+dx[i];
p.y=q.y+dir[i][];//p.y=q.y+dy[i]; while(p.x>=&&p.x<m&&p.y>=&&p.y<n&&map[p.x][p.y]!='*') //(新增)搜索完一个方向
{
if(!vis[p.x][p.y])
{
vis[p.x][p.y]=;
tp.push(p);
}
p.x+=dir[i][];//p.x+=dx[i]; //(新增)
p.y+=dir[i][];//p.y+=dy[i]; //(新增)
} } }
if(flag)
{
cout<<"yes\n";
}
else
{
cout<<"no\n";
}
} int main()
{
int t;
cin>>t;
while(t--)
{
cin>>m>>n;
for(int i=;i<m;i++)
{
for(int j=;j<n;j++)
{
cin>>map[i][j];
}
} point s,u;
cin>>k>>s.y>>s.x>>u.y>>u.x; s.y--;s.x--;u.y--;u.x--; memset(vis,,sizeof(vis)); //(新增)初始化访问标志的数组
bfs(s,u);
}
}
相关链接:http://blog.csdn.net/zhuhuangjian/article/details/8262561
最新文章
- 8.SVM用于多分类
- Spark-1.5.1 on CDH-5.4.7
- [原]openstack-kilo--issue(七):虚拟机怎么通外网,外网怎么ping通虚拟机
- 什么是jsonp
- apache AllowEncodedSlashes 允许URL中对路径分隔符进行编码
- spring事务认识
- profile工具
- Hive2.0函数大全(中文版)
- typeof 使用介绍
- Python 获得Facebook用户有一个共同的兴趣Friends
- ubuntu虚拟机和主机互ping及secureCRT使用
- git使用3
- openstack安装过程遇到的问题
- 【第六篇】SAP ABAP7.5x新语法之SQL注入
- VMware虚拟机中CentOS 7的硬盘空间扩容
- VS 开发必用插件
- php实现单点登录,顶级域名与子域名间共享Cookie实现单点登录原理
- pip 18.1: pipenv graph results in ImportError: cannot import name &#39;get_installed_distributions&#39;
- python 结构化数据解析
- Directly output the object name
热门文章
- hdu_2124 Flying to the Mars &; hdu_1800 Repair the Wall 贪心水题
- asp.net下载大文件代码
- layui模块化加载Echarts图表v4.2.1
- Get史上最优雅的加密方式!没有之一!
- 人工智能与VR结合:带来体验多样性
- 压缩工具gzip、bzip2、xz的使用
- Linux笔记(shell基础,历史命令,命令补全/别名,通配符,输出重定向)
- P5960 差分约束算法模板
- python json.dumps中ensure_ascii的使用,load与loads的区别
- 支付宝小程序云开发serverless----获取用户的user_id