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

  

时间: 08-22

poj3083 Children of the Candy Corn的相关文章

dfs/poj3083 Children of the Candy Corn

1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 5 using namespace std; 6 typedef pair<int,int>P; 7 const int dx[4]={1,0,-1,0}; 8 const int dy[4]={0,1,0,-1}; 9 const int INF=1e9; 10 int sx,sy,ex,ey,n,m; 11 char a[50][50];

POJ 3083 Children of the Candy Corn

Children of the Candy Corn Time Limit: 1000ms Memory Limit: 65536KB This problem will be judged on PKU. Original ID: 308364-bit integer IO format: %lld      Java class name: Main The cornfield maze is a popular Halloween treat. Visitors are shown the

K - Children of the Candy Corn

K - Children of the Candy Corn Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u Submit Status Description The cornfield maze is a popular Halloween treat. Visitors are shown the entrance and must wander through the maze fa

POJ 3083:Children of the Candy Corn(DFS+BFS)

Children of the Candy Corn Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 9311 Accepted: 4039 Description The cornfield maze is a popular Halloween treat. Visitors are shown the entrance and must wander through the maze facing zombies, ch

poj3083——dfs+bfs综合题

POJ 3083   dfs+bfs+模拟 Children of the Candy Corn Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 10564   Accepted: 4539 Description The cornfield maze is a popular Halloween treat. Visitors are shown the entrance and must wander through

poj3083

Children of the Candy Corn Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 12428   Accepted: 5353 Description The cornfield maze is a popular Halloween treat. Visitors are shown the entrance and must wander through the maze facing zombie

SELECT

CREATE TABLE CANDY_TBL SELECT * FROM PRODUCTS_TBL; INSERT INTO CANDY_TBL VALUES ( '9', 'CANDY CORN', 1.35 ); SELECT * FROM CANDY_TBL; +---------+-------------------------+-------+ | PROD_ID | PROD_DESC | COST | +---------+-------------------------+--

SQL入门经典插入表数据

MySQL EMPLOYEE_TBL INSERT INTO EMPLOYEE_TBL VALUES ('311549902','STEPHENS','TINA','DAWN','RR 3 BOX 17A','GREENWOOD','IN','47890','3178784465',NULL); INSERT INTO EMPLOYEE_TBL VALUES ( '442346889','PLEW','LINDA','CAROL','3301BEACON','INDIANAPOLIS','IN'

[CSS] Animating SVG

<!DOCTYPE> <html lang='en'> <head> <meta charset='utf-8'> <title>Cosplay Happenings</title> <link href='level4.css' rel='stylesheet' type='text/css'> </head> <body> <!-- Nav --> <nav class='na