逃离迷宫

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 34147 Accepted Submission(s): 8333

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, x₁, y₁, x₂, y₂ (1 ≤ k ≤ 10, 1 ≤ x₁, x₂ ≤ n, 1 ≤ y₁, y₂ ≤ m),其中k表示gloria最多能转的弯数，(x₁, y₁), (x₂, y₂)表示两个位置，其中x₁，x₂对应列，y₁, y₂对应行。

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，能往前走就往前走，输入行和列的时候看清楚啊，呜呜呜呜

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<map>

#include<set>

using namespace std;

#define INF 0x3f3f3f3f

const int maxn=;

int n,m;

int max_turn;

int start_x,start_y,end_x,end_y;

char a[maxn][maxn];

bool vis[maxn][maxn];

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

struct node

{

    int x,y;

    int turn_num;

};

int bfs()

{

    queue<node>que;

    node q1;

    q1.x=start_x;

    q1.y=start_y;

    q1.turn_num=-;

    que.push(q1);

    vis[start_x][start_y]=;

    while(!que.empty())

    {

        node q2=que.front();

        que.pop();

        if(q2.x==end_x && q2.y==end_y && q2.turn_num<=max_turn)

            return ;

        q1.turn_num=q2.turn_num+;

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

        {

            q1.x=q2.x+dir[i][];

            q1.y=q2.y+dir[i][];

            while(q1.x>= && q1.x<=n && q1.y>= && q1.y<=m && a[q1.x][q1.y]=='.' )

            {

                if(!vis[q1.x][q1.y])

                {

                    que.push(q1);

                    vis[q1.x][q1.y]=;

                }

                q1.x=q1.x+dir[i][];

                q1.y=q1.y+dir[i][];

            }

        }

    }

    return ;

}

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        cin>>n>>m;

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

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

                cin>>a[i][j];

        cin>>max_turn>>start_y>>start_x>>end_y>>end_x;

        memset(vis,,sizeof(vis));

        if(bfs())

            cout<<"yes"<<endl;

        else

            cout<<"no"<<endl;

    }

    return ;

}

巴特西

逃离迷宫 HDU - 1728（bfs）

逃离迷宫

最新文章

热门文章