【题目含义】若干次询问，每次有一个 $m\times n$ 的地图，上面每个格子若为 $0$ 则说明是可走的路，若不为 $0$ 则是小羊的家，如 $1$ 表示是 $1$ 号羊的家。后面有一个整数 $q$ ，表示 $q$ 次询问，每次给定 $4$ 个数 $a1$ $b1$ $a2$ $b2$，询问在 $(a1,b1)$ 的羊能否在拐第三个弯之前回到 $(a2,b2)$ 的家，可以输出 $YES$ ，否则输出 $NO$ 。
【思路】最少转弯问题。首先先输入数据，判断起点处 $A$ 和终点处 $B$ 是否满足 $A=B\neq0$，如果不满足说明不可能完成，直接输出 $NO$ ，否则进行广搜 $BFS$ 判断是否可行，可以输出 $YES$ ，否则输出 $NO$ 。
这里针对 $BFS$ 有个思路：

• 首先不要看到题目慌张，经过读题易知这道题目要对一个二维数组进行搜索，故先开好结构体 $\red{struct}\,\,\blue{node}$ ，里面成员有 $x$ 和 $y$ 坐标，以及最少拐弯次数。
• 接着就是 $BFS$ 过程的代码了。由于最少拐弯问题，如果一格一格搜索还要判断刚刚过来的方向与现在方向符不符合，太麻烦。不如，你直接往这个方向全部搜完都放入队列（比如 $(4,2)$ $(4,3)$ $(4,4)$ 这些格子在同一行或同一列，且都可以让小羊走，就一次性全加入队列， $\orange{turns}$ 拐弯次数 $+1$ 即可）。
• 然后，就到了 $BFS$ 队列第一个元素的赋值语句了。这里由于每次拐弯次数都要 $+1$ ，但如果一开始沿着直线走的话次数宜为 $0$ ，反推得到初始时赋值应当将 $\orange{turns}$ 结构体成员值赋值为 $-1$ 。
• 最后，如果成员 $\orange{turns} \leq 2$ 则判断是否需要继续 $BFS$ ，否则直接不加入队列（注意还不能 $\red{return}\,\,0;$ ）；当队列中已经没有元素时才能够 $\red{return}\,\,0;$ 。

$AC$ 代码

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=1000;
int n,m,k,a,b,c,d,e,graph[N][N],dir[4][2]={1,0,0,1,-1,0,0,-1};
struct node{
    int x,y,turns;
};
bool vis[N][N];
queue<node>q;
bool bfs(){
    //最少拐弯次数题——一次性全搜完不拐弯的情况
    q.push({a-1,b-1,-1});
    vis[a-1][b-1]=1;
    while(q.size()){
        node f=q.front();
        q.pop();
        if(f.turns<=2&&f.x==c-1&&f.y==d-1)return 1;//到达且拐弯次数不多于2
        else if(f.turns<2){
            for(int i=0;i<4;i++){
                int x=f.x,y=f.y;
                while(1){
                    x+=dir[i][0],y+=dir[i][1];
                    if(x<n&&x>=0&&y<m&&y>=0&&!vis[x][y]&&
                        (!graph[x][y]||graph[x][y]==graph[a-1][b-1])){
                        q.push({x,y,f.turns+1});
                        vis[x][y]=1;
                    }else break;
                }
            }
        }
    }
    return 0;
}
int main(){
    while(cin>>n>>m){
        if(n&&m){
            for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>graph[i][j];
            cin>>k;
            while(k--){
                cin>>a>>b>>c>>d;
                if(!graph[a-1][b-1]||!graph[c-1][d-1]||
                    graph[a-1][b-1]!=graph[c-1][d-1])
                    puts("NO");
                else{
                    memset(vis,0,sizeof(vis));
                    bool res=bfs();
                    puts(res?"YES":"NO");
                }
            }
        }else goto END;
    }
    END:
        return 0;
}