本题DFS与BFS都可以

就是判断在两次转弯后 能不能找到。。

BFS

#include<stdio.h>#include<string.h>#include<stdlib.h>#include<iostream>#include<queue>#include<algorithm>using namespace std;int a,b;int s[1005][1005];struct node{    int q,w,r,t;};int man[4][2]={0,1,-1,0,0,-1,1,0};int visit[1002][1002][4];int e1,f1;queue<node> q;node h,g;int bfs(){    while(!q.empty())    {        node yy=q.front();        //printf("%d %d %d %d\n",yy.q,yy.w,yy.r,yy.t);        q.pop();        //if(yy.t>2)           //continue;        //if(yy.q==e1&&yy.w==f1)        //{           // printf("YES\n");            //return 1;        //}        for(int i=0;i<4;i++)        {            h.q=yy.q+man[i][0];            h.w=yy.w+man[i][1];            if(h.q>0&&h.q<=a&&h.w<=b&&h.w>0&&visit[h.q][h.w][i]==0&&(s[h.q][h.w]==0||(h.q==e1&&h.w==f1)))            {                //printf("  %d  %d  \n",h.q,h.w);                 if(h.q==e1&&h.w==f1)                {                    printf("YES\n");                    return 1;                }                if(yy.r==-1||i==yy.r)                {                    h.r=i;                    h.t=yy.t;                    q.push(h);                    visit[h.q][h.w][i] = 1;                }                else                {                    h.r=i;                    h.t=yy.t+1;                    if(h.t>2)                        continue;                    q.push(h);                    visit[h.q][h.w][i] = 1;                }            }        }    }    return -1;}int main(){    int e,f,c;    while(~scanf("%d %d",&a,&b)){        if(a==0&&b==0)            break;        for(int i=1;i<=a;i++)            for(int j=1;j<=b;j++)            scanf("%d",&s[i][j]);        scanf("%d",&c);        while(c--)        {            memset(visit,0,sizeof(visit));            scanf("%d %d",&e,&f);            g.q=e;            g.w=f;            g.r=-1;            g.t=0;            scanf("%d %d",&e1,&f1);           // printf("%d\n",s[e1][f1]);            if(s[e][f]==0||s[e1][f1]==0||s[e][f]!=s[e1][f1])            {                printf("NO\n");                continue;            }            q.push(g);            int qq=bfs();            //printf("%d\n",qq);            if(qq==-1)                printf("NO\n");            while(!q.empty())                q.pop();        }    }    return 0;}

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int map[1005][1005], N, M, x1, x2, y1, y2, flag;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int vis[1005][1005];
void dfs(int x, int y, int count, int dir)
{
    if(flag)
        return;
    if(count >= 3)
        return;
    if(x == x2 && y == y2)
    {
        flag = 1;
        return;
    }
    if(x < 0 || y < 0 || x >= N || y >= M || map[x][y] != 0 || vis[x][y])
        return;
    if(count == 2)
    {
        if(!(dir==0&&y2==y&&x2<x||dir==1&&y2==y&&x2>x||dir==2&&y2<y&&x2==x||dir==3&&y2>y&&x2==x))
            return;
    }//很关键的剪枝，如果没有时间会达到3906MS或者超时~~
    vis[x][y] = 1;
    for(int i = 0; i < 4; i++)
    {
        if(i == dir)
            dfs(x + dx[i], y + dy[i], count, dir);
        else
            dfs(x + dx[i], y + dy[i], count+1, i);
    }
    vis[x][y] = 0;
}
int main()
{
    int ornum;
    while(scanf("%d%d", &N, &M) && (N || M))
    {
        for(int i = 0; i < N; i++)
            for(int j = 0; j < M; j++)
                scanf("%d", &map[i][j]);
        scanf("%d", &ornum);
        while(ornum--)
        {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            x1--; x2--; y1--; y2--;
            flag = 0;
            if((x1 != x2 || y1 != y2) && map[x1][y1] == map[x2][y2] && map[x1][y1] != 0)
            {
                memset(vis, 0, sizeof(vis));
                vis[x1][y1] = 1;
                for(i = 0; i < 4; i++)
                    dfs(x1 + dx[i], y1 + dy[i], 0, i);
            }
            if(flag)
                printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}