学步园

本题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;
}

百度的DFS代码

#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;
}