杭電 HDU ACM 1728 逃離迷宮

逃離迷宮

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 18241 Accepted Submission(s): 4409


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

草 今天這個破題 弄的我下午第一節都沒去上課，中午還被導員因為昨天晚自習西區省賽訓練逃課 訓了一頓！三千字檢討，靠 ，然後這個題 就因為一個細節錯誤wa一下午。 現在說說這個題，一般我們bfs的時候廣搜深度 和鄰接表相關，這個因為關注的是方向，我們可以認為轉0次彎是一層，1次彎是第二層…………按照這個規定bfs所到達的每個 結點的轉彎次數都是最少次數，我錯就錯在，一開始程序邏輯上並沒有一搜到底。而是遇到一個已經發現的結點然後 就不再往下遍歷了。悲劇啊。 AC：

#include
#include
#include
using namespace std;
int vis[101][101];
char cnt[101][101];
int t,m,n,k,x1,y1,y2,x2;
int dic[4][2]= {{0,1},{1,0},{0,-1},{-1,0}};

struct A
{
    int xx,yy;
    int step ;

} ;

void  bfs(int x,int y)
{
    A cur,next;
    queuels;
    vis[x][y]=1;
    cur.xx=x;
    cur.yy=y;
    cur.step=-1;
    ls.push(cur);

    while(!ls.empty())
    {
        cur=ls.front();
        ls.pop();

        if(cur.step>=k)  //如果上一次已經搜索完的那一行或列已經等於k的話那麼對於 這個結點其他方向的搜索，step肯定更大，直接break完事兒
            break;
        for(int i=0; i<4; i++)          //對於彈出的某個結點，我們深搜到底
        {
            next.xx=cur.xx+dic[i][0];
            next.yy=cur.yy+dic[i][1];
            next.step=cur.step+1;
            while(1)
            {

                if(cnt[next.xx][next.yy]!='*'&&next.xx>=0&&next.yy>=0&&next.xx>t;
    while(t--)
    {
        cin>>m>>n;
        for(int i=0; i>cnt[i][j];
        cin>>k>>x1>>y1>>x2>>y2;
        if(x1==x2&&y1==y2)            //注意兩點重合的情況
        {
            cout<<"yes"<