学步园

逃离迷宫

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2426    Accepted Submission(s): 566

Problem Description

　　给定一个
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₁
, y₁
, x₂
, y₂
(1 ≤ k ≤ 10, 1 ≤ x₁
, x₂
≤ n, 1 ≤ y₁
, y₂
≤ m),

其中
k

表示
gloria

最多能转的弯数，
(x₁
, y₁
), (x₂
, y₂
)

表示两个位置，其中
x₁

，
x₂

对应列，
y₁
, y₂

对应行。

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

刚看到题目的时候有人会立刻想到对四个方向一步一步进行
BFS,

其实这样是不行的
,

因为当从两条路径
BFS

到同一点的时候
,

要选择其中一个继续
BFS,

如果转弯数都相同的话
,

就很难判断哪条路径有可能通向终点
.

所以
,

这种方法行不通
.

而这题的解法就是对四个方向
BFS,

但不是一步一步
,

也就是搜一个方向的时候一直搜索到沿这个方向能走到的尽头
,

这样搜的话
,

能够保证搜过的路径的转弯次数都是最小的
(

因为这是基于转弯次数从
0

到
k

的
BFS).

#include<cstdio><br /> #include<queue><br /> #include<string.h><br /> using namespace std;<br /> int k,x1,x2,y1,y2,m,n,mark[105][105];<br /> struct point<br /> {<br /> int x,y;<br /> point operator + (point a)<br /> {<br /> point t;<br /> t.x=x+a.x;<br /> t.y=y+a.y;<br /> return t;<br /> }<br /> }p[5],v,que[1000000];<br /> bool fix(point v)<br /> {<br /> if ((v.x>=0)&&(v.x<n)&&(v.y>=0)&&(v.y<m)) return 1;<br /> return 0;<br /> }<br /> char g[105][105];<br /> int bfs()<br /> {<br /> int i;<br /> queue <point> que;<br /> point temp;<br /> v.x=x1;v.y=y1;<br /> que.push(v);<br /> while (!que.empty())<br /> {<br /> v=que.front();<br /> que.pop();<br /> for (i=1;i<=4;++i)<br /> {<br /> temp=v+p[i];<br /> while (fix(temp)&&(g[temp.y][temp.x]!='*'))<br /> {<br /> if (mark[temp.y][temp.x]==-1)<br /> {<br /> mark[temp.y][temp.x]=mark[v.y][v.x]+1;<br /> if ( temp.x==x2 && temp.y==y2 && mark[temp.y][temp.x]<=k ) return 1;<br /> que.push(temp);<br /> }<br /> temp=temp+p[i];<br /> }<br /> }<br /> }<br /> return 0;<br /> }<br /> int main()<br /> {<br /> int cas,i;<br /> p[1].x=1;p[1].y=0;<br /> p[2].x=-1;p[2].y=0;<br /> p[3].x=0;p[3].y=1;<br /> p[4].x=0;p[4].y=-1;<br /> scanf("%d",&cas);<br /> while (cas--)<br /> {<br /> memset(mark,-1,sizeof(mark));<br /> scanf("%d%d",&m,&n);<br /> gets(g[1]);<br /> for (i=0;i<m;i++)<br /> gets(g[i]);<br /> scanf("%d%d%d%d%d",&k,&x1,&y1,&x2,&y2);<br /> x1--;x2--;y1--;y2--;<br /> if ((x1==x2)&&(y1==y2)) printf("yes/n");<br /> else<br /> if (bfs()) printf("yes/n");<br /> else printf("no/n");<br /> }<br /> return 0;<br /> }<br />