HDU-1728 逃离迷宫

传送门：HUD - 1728

题目描述

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

输入描述

第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 ≤ x_1, x_2 ≤ n, 1 ≤ y_1, y_2 ≤ m)$,其中k表示gloria最多能转的弯数，$(x_1, y_1)$, $(x_2, y_2)$表示两个位置，其中x1，x2对应列，y1, y2对应行。

输出描述

每组测试数据对应为一行，若gloria能从一个位置走到另外一个位置，输出“yes”，否则输出“no”。

题意分析

常规做法会tle，必须剪枝。特别注意一下x1，x2对应列，y1, y2对应行

样例输入

2
5 5
...**
*.**.
.....
.....
*....
1 1 1 1 3
5 5
...**
*.**.
.....
.....
*....
2 1 1 1 3

样例输出

no
yes

AC代码

#include<bits/stdc++.h>
#pragma GCC optimize(2)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef map<int, int> mii;
typedef map<ll, ll> mll;

#define ull unsigned long long
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

const int maxn=1e6+10;
const ll mod=1e9+7;
const int INF = 0x3f3f3f3f;

int n,m,k,x1,y1,x2,y2,f;
int dx[4]= {1,-1,0,0},dy[4]= {0,0,1,-1};
char a[102][102];
int turn[102][102];

void dfs(int x,int y,int t) {
    if(x==x2&&y==y2&&turn[x][y]<=k) {
        f=1;
        return;
    }
    if(turn[x][y]>k)
        return;
    if(x!=x2&&y!=y2&&turn[x][y]==k)
        return;
    for(int i=0; i<4; i++) {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx<=0||ny<=0||nx>n||ny>m||a[nx][ny]=='*')
            continue;
        if(turn[nx][ny]<turn[x][y])
            continue;
        if(t!=-1&&i!=t&&turn[nx][ny]<turn[x][y]+1)
            continue;
        if(t!=-1&&i!=t)
            turn[nx][ny]=turn[x][y]+1;
        else
            turn[nx][ny]=turn[x][y];
        dfs(nx,ny,i);
        if(f)
            return;
    }
}


int main() {
    IOS;
    int t;
    cin>>t;
    while(t--) {
        f=0;
        cin>>n>>m;
        memset(a,0,sizeof(a));
        memset(turn,maxn,sizeof(turn));
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                cin>>a[i][j];
            }
        }
        cin>>k>>y1>>x1>>y2>>x2;
        turn[x1][y1]=0;
        dfs(x1,y1,-1);
        if(f)cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
}