hdu 1728 逃離迷宮 (DFS+轉彎數剪枝)

逃離迷宮

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 27063 Accepted Submission(s): 6598

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, 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

解析:

本題主要是剪枝問題。用的是轉彎數剪枝，用visit[x][y]來記錄在[x][y]的最小轉彎數,再用BFS

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define MAXN 300
#define inf 999999999
int n,m;
char map[MAXN][MAXN];
typedef struct local
{
    int x,y;
}loca;
loca direction[]={{,},{,},{-,},{,-}};
int visit[MAXN][MAXN];     //用于記錄起點到目前[x][y]位置的最小轉彎數
int d1,d2,q;



int check(loca tmp,int i)
{
    int x,y;
    x=tmp.x+direction[i].x;
    y=tmp.y+direction[i].y;
    if(x>=&&x<=n&&y>=&&y<=m)
    {
            if(map[x][y]=='.'||(x==d1&&y==d2))
            {
                return ;
            }
    }
    return ;
}

int dfs(loca tmp,int d)
{
    int i;
    loca oth;
    if(tmp.x==d1&&tmp.y==d2)
    {
        if(visit[tmp.x][tmp.y]<=q)
        return ;
    }

    if(visit[tmp.x][tmp.y]>q)return ;
    if(visit[tmp.x][tmp.y]==q)
    {
        if(tmp.x!=d1&&tmp.y!=d2)return ;
        if(tmp.x==d1&&(d%)!=)return ;   //？
        if(tmp.y==d2&&(d%)!=)return ;   //？
    }
    for(i=;i<;i++)
    {
        if(check(tmp,i))
        {
            oth.x=tmp.x+direction[i].x;
            oth.y=tmp.y+direction[i].y;
            if(visit[oth.x][oth.y]<visit[tmp.x][tmp.y])       //原來大于現在的剪掉，說明到達[x][y]還有更小的轉彎數的路徑
                continue;
            if(d!=-&&i!=d&&visit[oth.x][oth.y]<visit[tmp.x][tmp.y]+)   //轉彎+1之後原來的還是大于現在的轉彎數的話continue
                continue;                                                  //用i!=d因為防止其走回頭路
            visit[oth.x][oth.y]=visit[tmp.x][tmp.y];   //接受更小的轉彎數
            if(d!=-&&i!=d)visit[oth.x][oth.y]++;  //轉彎+1
            if(dfs(oth,i))return ;

        }
    }
    return ;
}

int main()
{
    int i,j,x0,y0,t;
    loca start;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(i=;i<=n;i++)
        {
            for(j=;j<=m;j++)
            {
                cin>>map[i][j];
            }
        }
        for(i=;i<=n;i++)
        {
            for(j=;j<=m;j++)
            {
                visit[i][j]=inf;
            }
        }
        cin>>q>>y0>>x0>>d2>>d1;
        if(map[d1][d2]=='*'||map[x0][y0]=='*')
        {
            printf("no\n");
            continue;
        }
        start.x=x0;
        start.y=y0;
        visit[x0][y0]=;
        if(dfs(start,-))
            printf("yes\n");
        else
            printf("no\n");
    }
    return ;
}