题目描述:输入一个m*n的地图,地图上有两种点,一种是 . 表示这个点是空地,是可以走的,另一种是 * ,表示是墙,是不能走的,然后输入一个起点和一个终点,另外有一个k输入,现在要你确定能否在转k次弯之前从起点到达终点。

解题报告:首先说下这题坑的地方,就是输入起点和终点的坐标的时候,不是按照x1,y1,x2,y2输入的,而是按照y1,x1,y2,x2的顺序输入的。这题搞了很久 ,就是一开始没有想到怎么解决得到最小转弯次数的方法,一开始试过重复访问点,但是这样超内存了,然后如果不重复访问的话又会得不到转弯次数最小的点,就是说假如一个点从一条路线上被更新过的话,下一次从另一条路线上就不能再一次更新了,即使如果按照第二次走的路线转弯的次数会更少的 话。看了别人解题报告才想到,可以这样来解决就是当走到一个点时,如果可以沿着这条线直走的话,就一直走下去,除非到了边界,或者碰到墙,同时是否将这点放入队列的话也要做出相应的 改变,因为走的时候只要不是墙都能走,但是 不能把所有的点都放进队列,所以我们可以将从没有走过并且是可以走的点放进队列,而把已经走过的点不放进队列,这样就可以解决超内存的问题了,另外,走完当前这个点之后,不要忘了把这个点标记为已经走过。并且每次走之前判断是否已经到达了终点、边界,墙。一开始用自己写的队列发现代码更长,时间也更长,后来改用deque双端队列来写,首先代码只写了5分钟,而且没有调试一次就AC了,并且时间更短,内存更小,代码也更短。这里把我手动写的队列的和用deque的代码都附上。

手写队列代码:

 #include<cstdio>
#include<cstring>
#include<time.h>
const int MAX = +;
int T,m,n,k,x1,y1,x2,y2;
int xx[] = {-,,,}; //定义移动方向
int yy[] = {,,,-};
int map[MAX][MAX];
typedef struct node {
int x,y,dire,time; //dire用来保存当前的方向,time表示走到当前步为止,转弯的次数
node() {
dire = time = ;
}
node *next;
}*LinkList,linklist;
bool bfs() {
LinkList head = NULL,p = NULL,temp;
head = new linklist; //新建队列头结点,头结点不放元素
p = new linklist; //便于存取节点
p->next = NULL;
p->x = x1,p->y =y1; //首先将起点加到队尾
head->next = p;
while(head->next!=NULL) {
temp = head->next; //将节点从队首取出
if(temp->x ==x2 && temp->y==y2 && temp->time-<k)
return true; //判断是否已经到达终点
for(int i = ;i<;++i) { //从当前的位置向周围四个方向走
int xxx = temp->x + xx[i];
int yyy = temp->y + yy[i];
if(xxx<||xxx>m||yyy<||yyy>n)
continue;
while(map[xxx][yyy]==||map[xxx][yyy]==) { //这一步很重要,如果当前走的方向是直的,且可走,则一直走到底,
//但只有从没有走过的点才加入到队列中
if(xxx<||xxx>m||yyy<||yyy>n)
break;
if(xxx ==x2 && yyy==y2 && temp->time-<k)
return true; LinkList q = new linklist;
q->next = NULL;
q->x = xxx;
q->y = yyy;
q->dire = i+;
q->time = temp->time;
if(temp->dire != q->dire)
q->time++;
if(!map[xxx][yyy]) { //从没走过的点才加入到队列中
q->next = p->next;
p->next = q;
p = p->next;
}
else delete q; //否则删除新建的这个点
map[xxx][yyy] = ; //走过之后标记为已走过,这一顺序,这句不能放前面
yyy+=yy[i];
xxx+=xx[i];
}
}
head->next = temp->next;
delete temp;
}
return false;
} int main() {
char d;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&m,&n);
memset(map,,sizeof(map));
for(int i = ;i<=m;++i) {
getchar();
for(int j = ;j<=n;++j) {
scanf("%c",&d);
if(d == '*')
map[i][j] = ;
}
}
scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);
printf(bfs()? "yes\n":"no\n");
}
return ;
}

deque代码:

 #include<cstdio>
#include<deque>
#include<iostream>
#include<cstring>
using namespace std;
const int MAX = +;
int k,x1,y1,x2,y2,m,n;
int xx[] = {-,,,};
int yy[] = {,,,-};
class node {
public:
int map[MAX][MAX];
bool bfs();
private:
struct Linklist {
int x,y,dire,times;
Linklist() {
dire = times = ;
}
};
};
bool node::bfs() {
deque<Linklist> head;
Linklist p;
p.x = x1,p.y = y1;
head.push_back(p);
deque<Linklist>::iterator iter;
while(head.size()!=) {
iter = head.begin();
for(int i = ;i<;++i) {
int xxx = iter->x + xx[i];
int yyy = iter->y + yy[i];
if(xxx<||xxx>m||yyy<||yyy>n)
continue;
while(map[xxx][yyy]!=) {
if(xxx == x2 && yyy ==y2 && iter->times-<k)
return true;
Linklist q;
q.x = xxx,q.y = yyy;
q.dire = i+;
q.times = iter->times;
if(q.dire != iter->dire)
q.times++;
if(map[xxx][yyy]==)
head.push_back(q);
map[xxx][yyy] = ;
xxx += xx[i];
yyy += yy[i];
if(xxx<||xxx>m||yyy<||yyy>n)
break;
}
}
head.pop_front();
}
return false;
}
int main() {
int T;
char c;
node temp;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&m,&n);
memset(temp.map,,sizeof(temp.map));
for(int i = ;i<=m;++i) {
getchar();
for(int j = ;j<=n;++j) {
scanf("%c",&c);
if(c == '*')
temp.map[i][j] = ;
}
}
scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);
printf(temp.bfs()? "yes\n":"no\n");
}
return ;
}

最新文章

  1. HttpClient (POST GET PUT)请求
  2. Oracle如何导出sys用户下的系统表
  3. 地理围栏算法解析(Geo-fencing)
  4. [PE结构分析] 5.IMAGE_OPTIONAL_HEADER
  5. java SE (java Standard Edition)
  6. 谈谈HttpUrlConnection与DefaultHttpClient一些区别
  7. U盘做启动盘后,如何恢复原始容量
  8. javascript取消disabled属性
  9. Flink Program Guide (9) -- StateBackend : Fault Tolerance(Basic API Concepts -- For Java)
  10. WASP_百度百科
  11. 自定义HttpFilter模块完善
  12. 我的Spring Boot学习记录(一):自动配置的大致调用过程
  13. Socket.io发送消息含义
  14. Java——String类中的compareTo方法总结
  15. ExceptionLess的webAPI调用
  16. Java的Unsafe类
  17. java 网络编程(四)TCP通讯
  18. hdu4847 Wow! Such Doge! KMP
  19. 基于Kafka消息驱动最终一致事务(一)
  20. 解决servlet-api包冲突问题(maven)

热门文章

  1. Spark读取Hbase的数据
  2. [工作中的设计模式]单例模式singleton
  3. linux安装,window上安装centos虚拟机
  4. MariaDB5.5.32 绿色版下载安装一条龙
  5. iOS Instruments之Core Animation动画性能调优(工具复选框选项介绍)
  6. code:blocks 编译环境设置
  7. ScrollView属性fillViewport解决android布局不能撑满全屏的问题
  8. 201521123114 《Java程序设计》第8周学习总结
  9. tree conflict svn 怎么解决
  10. Linux 64位下一键安装scipy等科学计算环境
  11. CF1059D Nature Reserve
  12. Analysis servlet
  13. 单总线(1-Wire Bus)技术及其应用
  14. .Net Core 在 Linux-Centos上的部署实战教程(四) ---- 总结
  15. BZOJ 1370: [Baltic2003]Gang团伙(luogu 1892)(种类并查集)
  16. ZigBee毕设
  17. Postfix 邮件服务 - roundcube webmail
  18. C#代码分析--阅读程序,回答问题
  19. JDK和CGLIB动态代理原理
  20. bzoj 3685: 普通van Emde Boas树