题目

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

Sample Output

no
yes

题解

BFS不记录距离，记录转的弯数

套用BFS模板即可

代码

/*
By:OhYee
Github:OhYee
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
using namespace std;

//DEBUG MODE
#define debug 0

//循环
#define REP(n) for(int o=0;o<n;o++)

const int maxn = 105;
int n,m;
char Map[maxn][maxn];
int dis[maxn][maxn];

typedef pair<int,int> point;

const int delta[] = {1,-1,0,0};

bool BFS(int s1,int s2,int v1,int v2,int k) {
    if(k < 0)
        return false;
    if(s1 == v1 && s2 == v2)
        return true;

    memset(dis,-1,sizeof(dis));
    queue<point> Q;

    Q.push(point(s1,s2));
    dis[s1][s2] = 0;
    while(!Q.empty()) {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();

        if(dis[x][y] == k+1)
            return false;

        REP(4) {
            int xx,yy;
            for(int i = 1;;i++) {
                xx = x + delta[o] * i;
                yy = y + delta[3 - o] * i;

                if(xx < 0 || xx > n || yy < 0 || yy > m || Map[xx][yy] == '*')
                    break;
                if(dis[xx][yy] == -1) {
                    dis[xx][yy] = dis[x][y] + 1;
                    if(xx == v1 && yy == v2)
                        return true;
                    Q.push(point(xx,yy));
                }


            }
        }
    }
    return false;

}

void Do() {
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n;i++)
        for(int j = 0;j < m;j++)
            scanf("\n%c\n",&Map[i][j]);
    int s1,s2,v1,v2,k;
    scanf("%d%d%d%d%d",&k,&s2,&s1,&v2,&v1);

    printf("%s\n",BFS(s1 - 1,s2 - 1,v1 - 1,v2 - 1,k) ? "yes" : "no");
}

int main() {
    int T;
    scanf("%d",&T);
    while(T--)
        Do();
    return 0;
}