逃離迷宮（bfs）

題意：給出一個圖和兩個點的坐标，以及一個整數k，求從一個點是否能在k次拐彎内到達另一個點

連結：

http://acm.hdu.edu.cn/webcontest/contest_showproblem.php?pid=1003&ojid=0&cid=10646&hide=0

思路：（參考網上代碼）用bfs隊列搜尋，從起點開始用一個循環每次搜同一個方向，符合條件的就入隊，跳出循環後計算拐彎次數的變量就加一。

代碼：

#include <iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
struct node
{
    int x,y,k;
};
char maze[][];
int next1[]= {,,-,};
int next2[]= {,-,,};
int vis[][];
int n,m,x1,x2,y1,y2,k;

void dfs(node s,node d)
{
    int flag=;
    queue<node> q;
    node v,w;
    v.x=s.x;
    v.y=s.y;
    v.k=-;//要注意是從-1開始
    vis[s.x][s.y]=;
    q.push(v);
    while(!q.empty())
    {
        v = q.front();
        q.pop();
        if(v.x == d.x && v.y == d.y && v.k <= k)
        {
            flag=;
            break;
        }
        w.k = v.k + ;
        for(int i=; i<; i++)
        {
            int dx=v.x+next1[i];
            int dy=v.y+next2[i];
            while(dx >=  && dx < n && dy >=  && dy < m && maze[dx][dy] == '.')//拐彎的問題這裡解決，一次性把一個方向的走完，跳出循環的話就意味着要拐彎了
            {
                if(!vis[dx][dy])
                {
                    vis[dx][dy]=;
                    w.x=dx;
                    w.y=dy;
                    q.push(w);
                }
                dx += next1[i];
                dy += next2[i];
            }
        }
    }
    if(flag)
        cout << "yes" << endl;
    else
        cout << "no" << endl;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        node s,d;
        cin >> n >> m;
        for(int i=; i<n; i++)
            scanf("%s",maze[i]);
        cin >> k;
        cin >> y1 >> x1 >> y2 >> x2;
        memset(vis, ,sizeof vis);
        s.x=x1-;
        s.y=y1-;
        d.x=x2-;
        d.y=y2-;
        dfs(s,d);
    }
    return ;
}
           

另：在自幾