Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

写了好长，复制粘贴改的手疼。0.0

Posted by lzh0108 at 2017-01-05 10:44:27 on Problem 3414

#include<stdio.h>
#include<string.h>
int a,b,c,flag;//flag标记是否成功找到结果
struct node
{
    char s[20];
    int x,y,behind,step;
} w[10100];
void print(int i)//回溯输出
{
    if(w[i].behind!=-1)
    {
        print(w[i].behind);
        printf("%s\n",w[i].s);
    }
}
int vis[110][110];
void bfs()
{
    int head=0,tail=1;
    w[0].x=0,w[0].y=0,w[0].behind=-1,w[0].step=0;
    vis[0][0]=1;
    while(head<tail)
    {
        node now=w[head];
     //   printf("now.x=%d now.y=%d now.step=%d \n",now.x,now.y,now.step);
        if(now.x==c||now.y==c)
        {
            flag=0;
            printf("%d\n",now.step);
            print(now.behind);
            printf("%s\n",now.s);
            break;
        }
        if(!vis[a][now.y]&&now.x==0)//FILL  a
        {
            vis[a][now.y]=1;
            w[tail].x=a;
            strcpy(w[tail].s,"FILL(1)");
            w[tail].behind=head;
            w[tail].step=now.step+1;
            w[tail].y=now.y;
            tail++;
        }
        if(now.x==a)
        {
            if(!vis[0][now.y])//DROP a
            {
                vis[0][now.y]=1;
                w[tail].x=0;
                strcpy(w[tail].s,"DROP(1)");
                w[tail].behind=head;
                w[tail].step=now.step+1;
                w[tail].y=now.y;
                tail++;
            }
            if(now.y!=b)//POUR(1,2)
            {
                if(now.x>(b-now.y)&&!vis[now.x-b+now.y][b])
                {
                    vis[now.x-b+now.y][b]=1;
                    w[tail].x=now.x-(b-now.y);
                    w[tail].y=b;
                    w[tail].behind=head;
                    w[tail].step=now.step+1;
                    strcpy(w[tail].s,"POUR(1,2)");
                    tail++;
                }
                else if(now.x<=(b-now.y)&&!vis[0][now.x+now.y])
                {
                    vis[0][now.x+now.y]=1;
                    w[tail].x=0;
                    w[tail].y=now.y+now.x;
                    w[tail].behind=head;
                    w[tail].step=now.step+1;
                    strcpy(w[tail].s,"POUR(1,2)");
                    tail++;
                }
            }
        }
        else if(now.x>0&&now.x<a)
        {
            if(!vis[a][now.y])//FILL 1
            {
                vis[a][now.y]=1;
                w[tail].x=a;
                strcpy(w[tail].s,"FILL(1)");
                w[tail].behind=head;
                w[tail].step=now.step+1;
                w[tail].y=now.y;
                tail++;
            }
            if(!vis[0][now.y])//DROP 1
            {
                vis[0][now.y]=1;
                w[tail].x=0;
                strcpy(w[tail].s,"DROP(1)");
                w[tail].behind=head;
                w[tail].step=now.step+1;
                w[tail].y=now.y;
                tail++;
            }
            if(now.y!=b)
            {
                if(now.x>(b-now.y)&&!vis[now.x-b+now.y][b])//POUR(1,2)
                {
                    vis[now.x-b+now.y][b]=1;
                    w[tail].x=now.x-(b-now.y);
                    w[tail].y=b;
                    w[tail].behind=head;
                    w[tail].step=now.step+1;
                    strcpy(w[tail].s,"POUR(1,2)");
                    tail++;
                }
                else if(now.x<=(b-now.y)&&!vis[0][now.x+now.y])//POUR(1,2)
                {
                    vis[0][now.x+now.y]=1;
                    w[tail].x=0;
                    w[tail].y=now.y+now.x;
                    w[tail].behind=head;
                    w[tail].step=now.step+1;
                    strcpy(w[tail].s,"POUR(1,2)");
                    tail++;
                }
            }
        }
        if(now.y==0&&!vis[now.x][b])//FILL 2
        {
            vis[now.x][b]=1;
            w[tail].y=b;
            strcpy(w[tail].s,"FILL(2)");
            w[tail].behind=head;
            w[tail].step=now.step+1;
            w[tail].x=now.x;
            tail++;
        }
        else if(now.y==b)
        {
            if(!vis[now.x][0])//DROP 2
            {
                vis[now.x][0]=1;
                w[tail].y=0;
                strcpy(w[tail].s,"DROP(2)");
                w[tail].behind=head;
                w[tail].step=now.step+1;
                w[tail].x=now.x;
                tail++;
            }
            if(now.x!=a)
            {
                if(now.y>(a-now.x)&&!vis[a][now.y-a+now.x])//POUR (2,1)
                {
                    vis[a][now.y-a+now.x]=1;
                    w[tail].y=now.y-(a-now.x);
                    w[tail].x=a;
                    w[tail].behind=head;
                    w[tail].step=now.step+1;
                    strcpy(w[tail].s,"POUR(2,1)");
                    tail++;
                }
                else if(now.y<=(a-now.x)&&!vis[now.x+now.y][0])//POUR (2,1)
                {
                    vis[now.x+now.y][0]=1;
                    w[tail].y=0;
                    w[tail].x=now.y+now.x;
                    w[tail].behind=head;
                    w[tail].step=now.step+1;
                    strcpy(w[tail].s,"POUR(2,1)");
                    tail++;
                }
            }
        }
        else if(now.y>0&&now.y<b)
        {
            if(!vis[now.x][b])//FILL 2
            {
                vis[now.x][b]=1;
                w[tail].y=b;
                strcpy(w[tail].s,"FILL(2)");
                w[tail].behind=head;
                w[tail].step=now.step+1;
                w[tail].x=now.x;
                tail++;
            }
            if(!vis[now.x][0])//DROP 2
            {
                vis[now.x][0]=1;
                w[tail].y=0;
                strcpy(w[tail].s,"DROP(2)");
                w[tail].behind=head;
                w[tail].step=now.step+1;
                w[tail].x=now.x;
                tail++;
            }

            if(now.x!=a)
            {
                if(now.y>(a-now.x)&&!vis[a][now.y-a+now.x])//POUR (2,1)
                {
                    vis[a][now.y-a+now.x]=1;
                    w[tail].y=now.y-(a-now.x);
                    w[tail].x=a;
                    w[tail].behind=head;
                    w[tail].step=now.step+1;
                    strcpy(w[tail].s,"POUR(2,1)");
                    tail++;
                }
                else if(now.y<=(a-now.x)&&!vis[now.x+now.y][0])//POUR (2,1)
                {
                    vis[now.x+now.y][0]=1;
                    w[tail].y=0;
                    w[tail].x=now.y+now.x;
                    w[tail].behind=head;
                    w[tail].step=now.step+1;
                    strcpy(w[tail].s,"POUR(2,1)");
                    tail++;
                }
            }
        }
        head++;
    }
}
int main()
{
    while(~scanf("%d%d%d",&a,&b,&c))
    {
        memset(vis,0,sizeof(vis));
        flag=1;
        bfs();
        if(flag)
            printf("impossible\n");
    }
    return 0;
}

Followed by:

Post your reply here:

User ID:
Password:
Title:

Content:

> #include<stdio.h>
> #include<string.h>
> int a,b,c,flag;//flag标记是否成功找到结果
> struct node
> {
>     char s[20];
>     int x,y,behind,step;
> } w[10100];
> void print(int i)//回溯输出
> {
>     if(w[i].behind!=-1)
>     {
>         print(w[i].behind);
>         printf("%s\n",w[i].s);
>     }
> }
> int vis[110][110];
> void bfs()
> {
>     int head=0,tail=1;
>     w[0].x=0,w[0].y=0,w[0].behind=-1,w[0].step=0;
>     vis[0][0]=1;
>     while(head<tail)
>     {
>         node now=w[head];
>      //   printf("now.x=%d now.y=%d now.step=%d \n",now.x,now.y,now.step);
>         if(now.x==c||now.y==c)
>         {
>             flag=0;
>             printf("%d\n",now.step);
>             print(now.behind);
>             printf("%s\n",now.s);
>             break;
>         }
>         if(!vis[a][now.y]&&now.x==0)//FILL  a
>         {
>             vis[a][now.y]=1;
>             w[tail].x=a;
>             strcpy(w[tail].s,"FILL(1)");
>             w[tail].behind=head;
>             w[tail].step=now.step+1;
>             w[tail].y=now.y;
>             tail++;
>         }
>         if(now.x==a)
>         {
>             if(!vis[0][now.y])//DROP a
>             {
>                 vis[0][now.y]=1;
>                 w[tail].x=0;
>                 strcpy(w[tail].s,"DROP(1)");
>                 w[tail].behind=head;
>                 w[tail].step=now.step+1;
>                 w[tail].y=now.y;
>                 tail++;
>             }
>             if(now.y!=b)//POUR(1,2)
>             {
>                 if(now.x>(b-now.y)&&!vis[now.x-b+now.y][b])
>                 {
>                     vis[now.x-b+now.y][b]=1;
>                     w[tail].x=now.x-(b-now.y);
>                     w[tail].y=b;
>                     w[tail].behind=head;
>                     w[tail].step=now.step+1;
>                     strcpy(w[tail].s,"POUR(1,2)");
>                     tail++;
>                 }
>                 else if(now.x<=(b-now.y)&&!vis[0][now.x+now.y])
>                 {
>                     vis[0][now.x+now.y]=1;
>                     w[tail].x=0;
>                     w[tail].y=now.y+now.x;
>                     w[tail].behind=head;
>                     w[tail].step=now.step+1;
>                     strcpy(w[tail].s,"POUR(1,2)");
>                     tail++;
>                 }
>             }
>         }
>         else if(now.x>0&&now.x<a)
>         {
>             if(!vis[a][now.y])//FILL 1
>             {
>                 vis[a][now.y]=1;
>                 w[tail].x=a;
>                 strcpy(w[tail].s,"FILL(1)");
>                 w[tail].behind=head;
>                 w[tail].step=now.step+1;
>                 w[tail].y=now.y;
>                 tail++;
>             }
>             if(!vis[0][now.y])//DROP 1
>             {
>                 vis[0][now.y]=1;
>                 w[tail].x=0;
>                 strcpy(w[tail].s,"DROP(1)");
>                 w[tail].behind=head;
>                 w[tail].step=now.step+1;
>                 w[tail].y=now.y;
>                 tail++;
>             }
>             if(now.y!=b)
>             {
>                 if(now.x>(b-now.y)&&!vis[now.x-b+now.y][b])//POUR(1,2)
>                 {
>                     vis[now.x-b+now.y][b]=1;
>                     w[tail].x=now.x-(b-now.y);
>                     w[tail].y=b;
>                     w[tail].behind=head;
>                     w[tail].step=now.step+1;
>                     strcpy(w[tail].s,"POUR(1,2)");
>                     tail++;
>                 }
>                 else if(now.x<=(b-now.y)&&!vis[0][now.x+now.y])//POUR(1,2)
>                 {
>                     vis[0][now.x+now.y]=1;
>                     w[tail].x=0;
>                     w[tail].y=now.y+now.x;
>                     w[tail].behind=head;
>                     w[tail].step=now.step+1;
>                     strcpy(w[tail].s,"POUR(1,2)");
>                     tail++;
>                 }
>             }
>         }
>         if(now.y==0&&!vis[now.x][b])//FILL 2
>         {
>             vis[now.x][b]=1;
>             w[tail].y=b;
>             strcpy(w[tail].s,"FILL(2)");
>             w[tail].behind=head;
>             w[tail].step=now.step+1;
>             w[tail].x=now.x;
>             tail++;
>         }
>         else if(now.y==b)
>         {
>             if(!vis[now.x][0])//DROP 2
>             {
>                 vis[now.x][0]=1;
>                 w[tail].y=0;
>                 strcpy(w[tail].s,"DROP(2)");
>                 w[tail].behind=head;
>                 w[tail].step=now.step+1;
>                 w[tail].x=now.x;
>                 tail++;
>             }
>             if(now.x!=a)
>             {
>                 if(now.y>(a-now.x)&&!vis[a][now.y-a+now.x])//POUR (2,1)
>                 {
>                     vis[a][now.y-a+now.x]=1;
>                     w[tail].y=now.y-(a-now.x);
>                     w[tail].x=a;
>                     w[tail].behind=head;
>                     w[tail].step=now.step+1;
>                     strcpy(w[tail].s,"POUR(2,1)");
>                     tail++;
>                 }
>                 else if(now.y<=(a-now.x)&&!vis[now.x+now.y][0])//POUR (2,1)
>                 {
>                     vis[now.x+now.y][0]=1;
>                     w[tail].y=0;
>                     w[tail].x=now.y+now.x;
>                     w[tail].behind=head;
>                     w[tail].step=now.step+1;
>                     strcpy(w[tail].s,"POUR(2,1)");
>                     tail++;
>                 }
>             }
>         }
>         else if(now.y>0&&now.y<b)
>         {
>             if(!vis[now.x][b])//FILL 2
>             {
>                 vis[now.x][b]=1;
>                 w[tail].y=b;
>                 strcpy(w[tail].s,"FILL(2)");
>                 w[tail].behind=head;
>                 w[tail].step=now.step+1;
>                 w[tail].x=now.x;
>                 tail++;
>             }
>             if(!vis[now.x][0])//DROP 2
>             {
>                 vis[now.x][0]=1;
>                 w[tail].y=0;
>                 strcpy(w[tail].s,"DROP(2)");
>                 w[tail].behind=head;
>                 w[tail].step=now.step+1;
>                 w[tail].x=now.x;
>                 tail++;
>             }
> 
>             if(now.x!=a)
>             {
>                 if(now.y>(a-now.x)&&!vis[a][now.y-a+now.x])//POUR (2,1)
>                 {
>                     vis[a][now.y-a+now.x]=1;
>                     w[tail].y=now.y-(a-now.x);
>                     w[tail].x=a;
>                     w[tail].behind=head;
>                     w[tail].step=now.step+1;
>                     strcpy(w[tail].s,"POUR(2,1)");
>                     tail++;
>                 }
>                 else if(now.y<=(a-now.x)&&!vis[now.x+now.y][0])//POUR (2,1)
>                 {
>                     vis[now.x+now.y][0]=1;
>                     w[tail].y=0;
>                     w[tail].x=now.y+now.x;
>                     w[tail].behind=head;
>                     w[tail].step=now.step+1;
>                     strcpy(w[tail].s,"POUR(2,1)");
>                     tail++;
>                 }
>             }
>         }
>         head++;
>     }
> }
> int main()
> {
>     while(~scanf("%d%d%d",&a,&b,&c))
>     {
>         memset(vis,0,sizeof(vis));
>         flag=1;
>         bfs();
>         if(flag)
>             printf("impossible\n");
>     }
>     return 0;
> }

Home Page Go Back To top