ACM-BFS之逃離迷宮——hdu1728

逃離迷宮

題目：http://acm.hdu.edu.cn/showproblem.php?pid=1728

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

Total Submission(s): 13583 Accepted Submission(s): 3224

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

廣搜題目，其實用深搜也可以做。

我剛開始向這道題 方向判斷用兩個數來代替，0代表列向，1代表橫向。

然後根據dis數組指派為 左、上、右、下，這樣i%2==0時則是列向行走，i%2==1時為橫向行走

經過實踐證明，這麼做時錯誤的。。o(╯□╰)o啊~~~~

好吧，關鍵在于，判斷一個點可以不可以走，不僅看它是否在界内或者是否是牆。

而是看曾經到達這個點的轉彎次數是否大于此次到達這個點的轉彎次數。

是以，如果曾經到達這個點最小轉彎次數等于這次到達這個點最小轉彎次數。

那也要将這個點入隊列。

就是說->到達一個點的轉彎次數相同，但兩次的方向可能不同。

So，如果用兩個方向來代替四個方向，則無法實作這種情況。

And，End

/*
Author：Tree
From： http://blog.csdn.net/lttree
逃離迷宮
hdu 1728
BFS——廣度優先搜尋
迷宮轉彎次數限定
*/
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
struct Coor
{
    int x,y,fx,tn;
};
int n,m,turn,f_x,f_y,dis[4][2]={-1,0,0,-1,1,0,0,1};
char mapp[101][101];
int vis[101][101];
bool isout(int x,int y)
{
    if( x<1 || x>n || y<1 || y>m )  return 1;
    if( mapp[x][y]=='*' )   return 1;
    return 0;
}
void bfs(int sx,int sy)
{
    int i;
    memset(vis,-1,sizeof(vis));
    queue <Coor> q;
    Coor pre,lst;

    pre.x=sx;
    pre.y=sy;
    pre.fx=-1;
    pre.tn=0;
    vis[pre.x][pre.y]=0;
    q.push(pre);

    while( !q.empty() )
    {
        pre=q.front();
        q.pop();
        for(i=0;i<4;++i)
        {
            lst.x=pre.x+dis[i][0];
            lst.y=pre.y+dis[i][1];
            // 判斷坐标是否越界或者撞牆等
            if( isout(lst.x,lst.y) )    continue;
            // 方向是否改變，-1代表它上一步是起點
            if( pre.fx!=-1 && pre.fx!=i )    lst.tn=pre.tn+1;
            else    lst.tn=pre.tn;

            if( lst.tn>turn )   continue;
            if(lst.x==f_x && lst.y==f_y)    {cout<<"yes"<<endl;return;}
            // 如果曾經到這裡轉彎次數大于這次到這裡轉彎次數，則該點可再進隊列
            if( vis[lst.x][lst.y]==-1 || vis[lst.x][lst.y]>=lst.tn )
            {
                lst.fx=i;
                vis[lst.x][lst.y]=lst.tn;
                q.push(lst);
            }
        }
    }
    cout<<"no"<<endl;
}

int main()
{
    int test,i,j,s_x,s_y;
    cin>>test;
    while(test--)
    {
        cin>>n>>m;
        for(i=1;i<=n;++i)
            for(j=1;j<=m;++j)
                cin>>mapp[i][j];
        // 注意别扭的輸入
        cin>>turn>>s_y>>s_x>>f_y>>f_x;
        bfs(s_x,s_y);
    }
    return 0;
}