学步园

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

http://acm.hdu.edu.cn/showproblem.php?pid=1728

 题解：此题和1175差不多，但此题转向次数不能确定，所以再和1175同样用DFS会超时,所以我只好把算法改成BFS了；

错误分析：1，DFS超时；不知道哪位大神用深搜解的此题，请详解；

     2，还有注意就是行列和1175相反；

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<queue>
#define MAX 105
using namespace std;
typedef struct node
{
    int x,y;
}node;
int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
char graph[MAX][MAX];
int n,m,x_s,y_s,x_e,y_e,qu;
int visit[MAX][MAX];
bool bfs()
{

    node s,next;
    memset(visit,-1,sizeof(visit));
    s.x=x_s;
    s.y=y_s;
    queue<node> q;//广搜需要建立队列
    q.push(s);
    while(!q.empty())
    {
        node pos=q.front();//取队首；
        q.pop();//队首元素出队列；
        int step=visit[pos.x][pos.y]+1;
         if(step>qu) break;//当转移次数大于所给定的qu时就推出循环，没有满足条件的路径，可以减少运行时间；
         for(int i=0;i<4;i++)
        {
            next.x=pos.x+dir[i][0];//转向
            next.y=pos.y+dir[i][1];
           while(next.x>=1&&next.x<=n&&next.y<=m&&next.y>=1&&graph[next.x][next.y]=='.')//沿着一个方向走到尽头；
            {
                if(visit[next.x][next.y]==-1)
                {
                    if(step<=qu&&next.x==x_e&&next.y==y_e)
                    return true;
                    q.push(next);
                    visit[next.x][next.y]=step;//这个定方向上的转移次数都是队首出列的转移次数+1；
                }
                next.x+=dir[i][0];//此时加的仍是的第i的方向；
                next.y+=dir[i][1];
            }
        }
    }
   return false;
}
int main()
{
    int i,j,t;
    scanf("%d",&t);
    while(t--)
    {
        memset(visit,0,sizeof(visit));
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
        {
            getchar();
            for(j=1;j<=m;j++)
            scanf("%c",&graph[i][j]);
        }
        scanf("%d",&qu);
        scanf("%d%d%d%d",&y_s,&x_s,&y_e,&x_e);
        if(graph[x_s][y_s]!=graph[x_e][y_e])
        {
            printf("no\n");
            continue;
        }
        if(x_s==x_e&&y_s==y_e)
        {
            printf("yes\n");
            continue;
        }

        if(bfs())printf("yes\n");
        else printf("no\n");
    }
    return 0;
}