逃离迷宫

 

逃离迷宫

给定一个m × n (m行, n列)的迷宫,迷宫中有两个位置,gloria想从迷宫的一个位置走到另外一个位置,当然迷宫中有些地方是空地,gloria可以穿越,有些地方是障碍,她必须绕行,从迷宫的一个位置,只能走到与它相邻的4个位置中,当然在行走过程中,gloria不能走到迷宫外面去。令人头痛的是,gloria是个没什么方向感的人,因此,她在行走过程中,不能转太多弯了,否则她会晕倒的。我们假定给定的两个位置都是空地,初始时,gloria所面向的方向未定,她可以选择4个方向的任何一个出发,而不算成一次转弯。gloria能从一个位置走到另外一个位置吗?

Input

第1行为一个整数t (1 ≤ t ≤ 100),表示测试数据的个数,接下来为t组测试数据,每组测试数据中,

第1行为两个整数m, n (1 ≤ m, n ≤ 100),分别表示迷宫的行数和列数,接下来m行,每行包括n个字符,其中字符’.’表示该位置为空地,字符’*’表示该位置为障碍,输入数据中只有这两种字符,每组测试数据的最后一行为5个整数k, x 1, y 1, x 2, y 2 (1 ≤ k ≤ 10, 1 ≤ x 1, x 2 ≤ n, 1 ≤ y 1, y 2 ≤ m),其中k表示gloria最多能转的弯数,(x 1, y 1), (x 2, y 2)表示两个位置,其中x 1,x 2对应列,y 1, y 2对应行。

Output

每组测试数据对应为一行,若gloria能从一个位置走到另外一个位置,输出“yes”,否则输出“no”。

Sample Input

 2 5 5 ...** *.**. ..... ..... *.... 1 1 1 1 3 5 5 ...** *.**. ..... ..... *.... 2 1 1 1 3

Sample Output

 no yes

中文题的题意还是很好懂的,就是从一个点到另外一个点,限制了拐弯次数,看你能否到达。主函数和别的搜索一样都是先把图录进去,然后清零标记数组,标记清零,做好输出和调用函数的准备。他的不一样在于你搜索时候的方法,写道判断条件返回值的时候还都一样,就是他这个拐弯,你得特殊处理一下,我在那里把以前的if条件换成了while循环,让他沿着这个方向走下去,然后把可以走的点给压缩队列,每个方向都这样,这样就知道他的拐弯次数了。

#include

#include

#include<queue>

#include

using namespace std;

char a[1010][1010];

int book[1010][1010];

int n,m,k,x1,y1,x2,y2,flag;

int step[4][2]= {1,0,0,-1,-1,0,0,1};

struct node

{

int x,y,turn;

};

void bfs()

{

queueQ;

node now,next,future;

now.x=x1-1;

now.y=y1-1;

now.turn=-1;

book[x1-1][y1-1]=1;

Q.push(now);

while(!Q.empty())

{

now=Q.front();

Q.pop();

if(now.x==x2-1&&now.y==y2-1&&now.turn<=k)

{

flag = 1;

return ;

}

for(int i=0;i<4;i++)

{

next.x=now.x+step[i][0];

next.y=now.y+step[i][1];

while(0<=next.x&&next.x

{

if(book[next.x][next.y]==0)

{

next.turn = now.turn+1;

book[next.x][next.y] = 1;

Q.push(next);

}

future.x=next.x+step[i][0];

future.y=next.y+step[i][1];

next=future;

}

}

}

}

int main()

{

int w;

scanf(“%d”,&w);

while(w–)

{

scanf(“%d%d”,&n,&m);

for(int i=0; i

scanf(“%s”,a[i]);

memset(book,0,sizeof(book));

scanf(“%d%d%d%d%d”,&k,&y1,&x1,&y2,&x2);

flag=0;

bfs();

if(flag)

printf(“yesn”);

else

printf(“non”);

}

return 0;

}

相关阅读

走迷宫

这里面的由递归打印路径到非递归实现路径打印,十分好 #include #include #include #include

凛冬将至:品牌和传统零售商如何逃离倒闭潮?

国内外的零售业都在感受着“凛冬到来的残酷”,传统零售业迎来关店潮。关店潮的背后,是实体零售业所面临的巨大危机。那么品牌和传统

逃离“to-do清单怪圈”:关注优先事项,不要在意时间

找到高效时间段,不要列徒有虚名的待办事项清单。经营一家公司,每天都会遇到很多事情。其中,不乏比较重要又比较紧急的事情。对此,我们

邮件门的迷宫 希拉里邮件数据探索

摘要: 11月9日中午,不关心也不懂政治的我忽然非常感动,多少,我们在朋友圈的直播里见证了一个以一敌万的故事,这不是武侠小说,也不是好

【POJ1383】BFS,迷宫,最长路

LabyrinthTime Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu Submit StatusDescription

发表评论