HDOJ1728(限制转弯的迷宫问题)

用bfs进行深搜,求出每个可达点的最小转弯数

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int MAX_N=;

char g[MAX_N][MAX_N];

int vis[MAX_N][MAX_N];

int n,m;

int k,sx,sy,ex,ey;

struct node{

    int x,y,turns;

    node(){}

    node(int cy,int cx,int cturns):x(cx),y(cy),turns(cturns){}

};

int dx[]={,,-,};

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

bool judge(int r,int c)

{

    if(<=r&&r<=m&&<=c&&c<=n&&g[r][c]=='.')

    {

        return true;

    }

    return false;

}

void bfs()

{

    if(sy==ey&&sx==ex)

    {

        printf("yes\n");

        return;

    }

    queue<node> que;

    que.push(node(sy,sx,-));

    vis[sy][sx]=;

    while(!que.empty())

    {

        node now=que.front();que.pop();

        for(int i=;i<;i++)

        {

            int ny=now.y+dy[i];

            int nx=now.x+dx[i];

            while(judge(ny,nx))//按一条路深搜

            {

                if(!vis[ny][nx])

                {

                //    printf("%c (%d,%d) %d\n",g[ny][nx],ny,nx,now.turns+1);

                    que.push(node(ny,nx,now.turns+));

                    vis[ny][nx]=;

                    if(ny==ey&&nx==ex&&now.turns+<=k)

                    {

                        printf("yes\n");

                        return ;

                    }

                }

                ny+=dy[i];

                nx+=dx[i];

            }

        }

    }

    printf("no\n");

}

int main()

{

    int t;scanf("%d",&t);

    while(t--)

    {

        memset(vis,,sizeof(vis));

        scanf("%d %d",&m,&n);

        scanf("%*c");

        for(int i=;i<=m;i++)

        {

            for(int j=;j<=n;j++)

            {

                scanf("%c",&g[i][j]);

            }

            scanf("%*c");

        }

        scanf("%d %d %d %d %d",&k,&sx,&sy,&ex,&ey);

        bfs();

    }

    return ;

}