hdu 1728

//hdu 1728

//这个是一道很经典的迷宫题了，思路感觉。。。取起点和终点，判断连线是否超过n个弯，

//先是从起点出发，上下左右四个方向搜索，找到一条路，把那条路的第一个点压入队列

//然后沿着那个方向一直搜下去，直到不符合条件（4个方向都动不了），就从队列里面去首元素

//然后不断循环这个操作。。。。

#include <iostream>

#include <cstring>

#include <queue>

#include <stdio.h>

#include <algorithm>

using namespace std;

char Map[110][110];

int vis[110][110];

int dx[]={0,0,-1,1};//两个数组是搜索的时候用

int dy[]={-1,1,0,0};

int k,x1,x2,y1,y2,i,side1,side2;

struct dot

{

    int x,y,k;//k存放转弯数

};

void BFS(dot a,dot b)

{

    int flag=0;  vis[a.x][a.y]=1;//flag标记是否到达目标

    dot m,n;     m.x=a.x; m.y=a.y; m.k=-1;//m,n为中间变量

    queue<dot>q;  q.push(m);//将起点a（m）入队列

    while(!q.empty())//别问为什么要用队列非空来做。。。书上写的，记住就ok，因为你还不是大牛

    {

        m=q.front();

        q.pop();

        if(m.x==b.x&&m.y==b.y&&m.k<=k)   {flag=1;  break;}

        n.k=m.k+1;//因为每次从队列取出首元素，这个时候已经增加了一个弯

        for(i=0;i<4;i++)//开始搜索

        {

            int j=m.x+dx[i];

            int l=m.y+dy[i];

            while(j>=0&&j<side1&&l>=0&&l<side2&&Map[j][l]!='*')//判断条件

            {

                if(!vis[j][l])

                {

                    vis[j][l]=1;

                    n.x=j;

                    n.y=l;

                    q.push(n);//如果没被标记，那么标记它，用n记下此时坐标值，压入队列中

                }

                j+=dx[i];//朝某个方向一直搜索

                l+=dy[i];

            }

        }

    }

    if(flag==1)  cout<<"yes\n";

    else

        cout<<"no\n";

}

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        memset(vis,0,sizeof(vis));

        //memset(Map,0,sizeof(Map));

        dot _m,_n;

        cin>>side1>>side2;

        for(i=0;i<side1;i++)

            cin>>Map[i];

        cin>>k>>y1>>x1>>y2>>x2;//要注意这个地方好坑人。。。。。

        _m.x=x1-1;  _m.y=y1-1;

        _n.x=x2-1;  _n.y=y2-1;

        BFS(_m,_n);

    }

    return 0;

}