HDU 1175 连连看【BFS】

题意：给出起点和终点的棋子，不能经过别的棋子，而且转弯的次数不能超过2次，问能否消除

和逃离迷宫一样，每个节点记录下来它的当前的方向和转弯的次数，再搜

注意特判起点的棋子和终点的棋子为0或者不一样的情况，这样的话就不用搜了，直接输出NO

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 const int INF = (<<)-;

 const int mod=;

 const int maxn=;

 int g[][];

 int turn[][];

 int n,m;

 int dir[][]={,,-,,,,,-};

 struct node{

     int x,y;

     int turn;

     int dir;

 };

 node st,en;

 void bfs(){

     queue<node> q;

     node u;

     u.x=st.x;u.y=st.y;u.turn=;u.dir=-;

     turn[u.x][u.y]=;

     q.push(u);

     while(!q.empty()){

         u=q.front();q.pop();

         node v;

         for(int i=;i<;i++){

             v.x=u.x+dir[i][];

             v.y=u.y+dir[i][];

             v.turn=u.turn;

             v.dir=u.dir;

             if(u.x==en.x&&u.y==en.y&&u.turn<=){

                 printf("YES\n");

                 return;

             }

             if(v.dir!=i&&v.dir!=-) v.turn++;

             if(v.x==en.x&&v.y==en.y&&v.turn<=){

                 printf("YES\n");

                 return;

             }

             if(v.x<||v.x>n||v.y<||v.y>m||g[v.x][v.y]!=) continue;

             if(v.turn>) continue;

             if(v.turn<=turn[v.x][v.y]){

                 turn[v.x][v.y]=v.turn;

                 v.dir=i;

                 q.push(v);

             }

         }

     }

     printf("NO\n");

 }

 int main(){

     while(scanf("%d %d",&n,&m)!=EOF&&n&&m){

         for(int i=;i<=n;i++){

             for(int j=;j<=m;j++) cin>>g[i][j];

         }

         int q;

         scanf("%d",&q);

         while(q--){

             for(int i=;i<=n;i++)

              for(int j=;j<=m;j++) turn[i][j]=;

             scanf("%d %d %d %d",&st.x,&st.y,&en.x,&en.y);

             if(g[st.x][st.y]!=g[en.x][en.y]||!g[st.x][st.y]||!g[en.x][en.y]) printf("NO\n");

             else bfs();

         }

     }

     return ;

 }