#include
#include
#include
using namespace std;
typedef pairp;
char migong[100][100];//迷宫
int bj[100][100];//迷宫每到达每一个位置所要的步数
int zx[100][100];//到达每一个位置所进行的转向的次数
p zhuangtai[100][100];//记录每一个位置的状态，方便做是否转向的判断
const int M = 100000;
int n, m;//迷宫的大小
int sx, sy;//迷宫的起点
int dx, dy;//迷宫的终点
int k; //k表示转向的最大次数
void show()
{
int i, j;/*
for (i = 0; i < n; i++)
{
for (j = 0; j < m; j++)
cout <
cout
}
cout
for (i = 0; i
{
for (j = 0; j
cout
cout
}
cout
}
bool bfs()
{
queue
pp;
pp.push(p(sx, sy));
bj[sx][sy] = 0;
zx[sx][sy] = -1;//起点处的转弯次数为-1，这样走出的第一步转弯次数为0
zhuangtai[sx][sy] = p(0, 0);
while (pp.size())
{
//show();
int x = pp.front().first;
int y = pp.front().second;
if (pp.front().first == dx&&pp.front().second == dy&&zx[x][y]<=k)
{
//cout << "到达终点，并且转弯次数没有超限" << endl;
return true;
}
/*if (pp.front().first == dx&&pp.front().second == dy)
{
cout << zx[pp.front().first][pp.front().second] << endl;
cout << "到达终点，但是转弯次数超限" << endl;
}*/
int a[4] = { 0, 0, 1, -1 }, b[4] = { 1, -1, 0, 0 };
int i;
for (i = 0; i < 4; i++)
{
int tempx = x + a[i];
int tempy = y + b[i];
if (migong[tempx][tempy] == '.' && 0 <= tempx&&tempx < n && 0 <= tempy&&tempy < m && ((bj[tempx][tempy] > bj[x][y]&&zx[tempx][tempy]>zx[x][y]) || zx[tempx][tempy] > zx[x][y]))
{
bj[tempx][tempy] = bj[x][y] + 1;
zhuangtai[tempx][tempy] = p(tempx-x, tempy-y);
if (p(tempx - x, tempy - y) != zhuangtai[x][y])
{
zx[tempx][tempy] = zx[x][y] + 1;
}
else
zx[tempx][tempy] = zx[x][y];
pp.push(p(tempx, tempy));
}
}
pp.pop();
}
return false;
}
int main()
{
int z;
cin >> z;
while (z--)
{
//int n, m;
cin >> n >> m;
int i, j;
for (i = 0; i < n; i++)
{
for (j = 0; j < m; j++)
{
cin >> migong[i][j];
bj[i][j] = M;
zx[i][j] = M;
}
}
cin >> k >> sy >> sx >> dy >> dx;
sy--; sx--; dy--; dx--;
if (migong[sx][sy] == '*'){
cout << "no" << endl;
continue;
}
if (bfs())
cout << "yes" << endl;
else
cout << "no" << endl;
}
return 0;
}
下面是题目：
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, x1, y1, x2, y2 (1 ≤ k ≤ 10, 1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m),其中k表示gloria最多能转的弯数，(x1, y1), (x2, y2)表示两个位置，其中x1，x2对应列，y1, y2对应行。
Output
每组测试数据对应为一行，若gloria能从一个位置走到另外一个位置，输出“yes”，否则输出“no”。
Sample Input
2
5 5
...**
.*.
.....
.....
....
1 1 1 1 3
5 5
...*
.*.
.....
.....
*....
2 1 1 1 3
