hdu 1728 逃離迷宮（BFS）

之前用DFS做的，結果超時，看了別人的做法才做出來，現在用BFS做了，明顯感覺用BFS容易多了

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
char map[105][105];
int v[105][105];//記錄起點到達每個點的最少轉彎次數
int d[4][2] = { {1,0},{-1,0},{0,-1},{0,1} };
int begin_x,begin_y,end_x,end_y;
int flag,n,m,num;
struct node
{
    int x,y;
    int change_d;//記錄改變方向的次數
    int d;//記錄方向
};
void bfs()
{
    queue <node> q;
    node s,temp;
    s.x = begin_x;
    s.y = begin_y;
    s.change_d = 0;
    s.d = -1;
    v[s.x][s.y] = 0;//起點轉彎數
    q.push(s);
    while(!q.empty())
    {
        temp = q.front();
        q.pop();
        if(temp.x == end_x && temp.y == end_y && temp.change_d <= num)
        {
            printf("yes\n");
            flag = 1;
            return ;
        }
        for(int i = 0 ; i < 4 ; i ++)
        {
            s = temp;
            s.x += d[i][0];
            s.y += d[i][1];
            if(s.x < 0 || s.x >= n || s.y < 0 || s.y >= m || map[s.x][s.y] == '*') continue;
            /*s.d！=-1表示不在起點處，在起點處往哪個方向都可以，轉彎次數不增加*/
            if(s.d != -1 && i != s.d)//i=0,1,2,3分別表示不同的方向
             s.change_d ++;
            s.d = i;
            if(s.change_d > num) continue;
            if(s.change_d <= v[s.x][s.y])
            {
                v[s.x][s.y] = s.change_d;
                q.push(s);
            }
        }
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    int i,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(i = 0 ; i < n  ; i ++)
          scanf("%s",map[i]);
        scanf("%d%d%d%d%d",&num,&begin_y,&begin_x,&end_y,&end_x);
        begin_x--;  begin_y--;  end_x--;  end_y--;//題目給出的行和列都是從1開始計算的，不是從0
        memset(v,1,sizeof(v));//先將轉彎數初始化最大值
        flag = 0;
        bfs();
        if(!flag) printf("no\n");
    }
    return 0;
}