poj3083 Children of the Candy Corn 深搜+广搜

这道题有深搜和广搜。深搜还有要求，靠左或靠右。下面以靠左为例，可以把简单分为上北，下南，左西，右东四个方向。向东就是横坐标i不变，纵坐标j加1（i与j其实就是下标）。其他方向也可以这样确定。通过上一步方向可以确定下一步应该从哪个方向开始搜。比如说，是向北走的，就必须先搜西，西不可以走，再搜北，如果北还不可以走，再搜东，最后才是南。其他方向的情况也可以这样推出来。最后走到E点完成了。广搜就是最基础的广搜。这道题做了将近10个小时。中途曾几次准备放弃，但最后还是坚持做完了。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

#include<algorithm>

using namespace std;

char maze[40][40];

int n,m,ex,ey,sx,sy,flag,s,cx,cy,df;

int dlx[7]={0,1,0,-1,0,1,0};

int dly[7]={1,0,-1,0,1,0,-1};

int drx[7]={0,-1,0,1,0,-1,0};

int dry[7]={1,0,-1,0,1,0,-1};

int dx[4]={0,0,1,-1};

int dy[4]={1,-1,0,0};

int isin(int x,int y)

{

    return x>=0&&x<n&&y>=0&&y<m;

}

void lfs(int i,int j)

{

    int x,y,k;

    if(flag) return ;

    if(i==ex&&j==ey) {flag=1;}

    else

    for(k=df;k<7&&!flag;k++)

    {

        cx=dlx[k];

        cy=dly[k];

        x=i+dlx[k];

        y=j+dly[k];

        if(isin(x,y)&&maze[x][y]!='#'){

            s++;

             if(cx==1) df=0;

            //往南的，先搜东

            else if(cx==-1) df=2;

            //往北的，先搜西

            else if(!cx){

            if(cy==1) df=3;

            //往东的，先搜北

            else df=1;

        }

            //printf("(%d %d) ",x,y);

            lfs(x,y);

        }

    }

}

void rfs(int i,int j)

{

    int x,y,k,d;

    if(flag) return ;

    if(i==ex&&j==ey) {flag=1;}

    else

    for(k=df;k<7&&!flag;k++)

    {

        cx=drx[k];

        cy=dry[k];

        x=i+drx[k];

        y=j+dry[k];

        if(isin(x,y)&&maze[x][y]!='#'){

            s++;

             if(cx==1) df=2;

            //往南的，先搜西

            else if(cx==-1) df=0;

            //往北的，先搜东

            else if(!cx){

            if(cy==1) df=3;

            //往东的，先搜南

            else df=1;

        }

            //printf("(%d %d) ",x,y);

            rfs(x,y);

        }

    }

}

struct node

{

    int dis,row,col;

};

queue<node> q;

void  bfs()

{

    int x,y,k,d,i,j;

    node t;

    while(!q.empty())

    {

        t=q.front();

        q.pop();

        d=t.dis;

        i=t.row;

        j=t.col;

        for(k=0;k<4;k++)

        {

            x=i+dx[k];

            y=j+dy[k];

            if(maze[x][y]!='#'&&isin(x,y)){

                if(x==ex&&y==ey){

                    s=d+1;

                    return ;

                }

                else{

                    t.dis=d+1;

                    t.row=x;

                    t.col=y;

                    q.push(t);

                    maze[x][y]='#';

                }

            }

        }

    }

}

int main()

{

    int ca,i,j;

    scanf("%d",&ca);

    while(ca--)

    {

        scanf("%d%d",&m,&n);

        getchar();

        for(i=0;i<n;i++) gets(maze[i]);

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

            for(j=0;j<m;j++){

                if(maze[i][j]=='S'){

                    sx=i;sy=j;

                    maze[sx][sy]='#';

                }

                else if(maze[i][j]=='E'){

                    ex=i;ey=j;

                    maze[ex][ey]='.';

                }

            }

        }

        flag=0;

        s=1;

        if(!sy) df=3;

        else if(!sx) df=0;

        else if(sy==m-1) df=1;

        else if(sx==n-1) df=2;

        lfs(sx,sy);

        if(!sy) df=3;

        else if(!sx) df=0;

        else if(sy==m-1) df=1;

        else if(sx==n-1) df=2;

        cout<<s<<' ';

        flag=0;

        s=1;

        rfs(sx,sy);

        cout<<s<<' ';

        while(!q.empty()) q.pop();

        node p;

        p.dis=1;

        p.row=sx;

        p.col=sy;

        q.push(p);

        s=1;

        bfs();

        cout<<s<<endl;

    }

    return 0;

}

巴特西

poj3083 Children of the Candy Corn 深搜+广搜

最新文章

热门文章