HDU 1728 逃离迷宫(DFS||BFS)

逃离迷宫

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

 

Answer(仅dfs)

这个题目看起来就是连连看，写起来其实也是连连看，但是单纯地这样写会超时，那么需要一个剪枝--最小转弯次数。

用mark数组保存某个点的转弯次数，当再次走到这个点的时候判断目前的转弯次数是否小于之前走到这个点时的转弯次数，否则直接return。

 

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m;
int k,x1,y1,x2,y2,flag;
char mp[120][120];
int mark[120][120];//转弯次数
int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}};
void dfs(int x,int y,int dire)
{
    if(mark[x][y]>k)return;
    if(x==x2&&y==y2)
    {
        if(mark[x][y]<=k)flag=1;
        return;
    }
    if(mark[x][y]==k&&x!=x2&&y!=y2)
        return;
    if(flag)return;
    for(int i=0; i<4; i++)
    {
        int nx=x+dir[i][0];
        int ny=y+dir[i][1];
        if(nx<0||ny<0||nx>=n||ny>=m)
            continue;
        if(mp[nx][ny]=='*'||mark[nx][ny]<mark[x][y]) //重要剪枝
            continue;
        if(dire!=-1&&i!=dire&&mark[nx][ny]<mark[x][y]+1)
            continue;
        mark[nx][ny]=mark[x][y];
        if(dire!=-1&&i!=dire)
            mark[nx][ny]++;
        dfs(nx,ny,i);
        if(flag)
            return;
    }
}
int main()
{
    int N;
    cin>>N;
    while(N--)
    {
        cin>>n>>m;
        flag=0;
        for(int i=0; i<n; i++)
            cin>>mp[i];
        cin>>k>>y1>>x1>>y2>>x2;
        memset(mark,1,sizeof mark);
        x1--,x2--,y1--,y2--;
        mark[x1][y1]=0;
        dfs(x1,y1,-1);
        if(flag)printf("yes
");
        else printf("no
");
    }
    return 0;
}