HDU 1782.逃离迷宫

467


题目



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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论