Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

POJ测试数据确实很边缘化,用100*100的数组就是过不了,上代码

Posted by hrbust_caozhenhai at 2012-03-22 20:14:21 on Problem 3414
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
bool map[105][105];
char op[6][15]={"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};
int a,b,c;
struct point
{
    int x,y;
    int step;
};
struct point2
{
    int fx,fy;
    int oper;
};
point2 opera[105][105];
point fill1(point t)
{
    point temp;
    temp.x=a;
    temp.y=t.y;
    temp.step=t.step+1;
    return temp;
}
point fill2(point t)
{
    point temp;
    temp.x=t.x;
    temp.y=b;
    temp.step=t.step+1;
    return temp;
}
point drop1(point t)
{
    point temp;
    temp.x=0;
    temp.y=t.y;
    temp.step=t.step+1;
    return temp;
}
point drop2(point t)
{
    point temp;
    temp.x=t.x;
    temp.y=0;
    temp.step=t.step+1;
    return temp;
}
point pour1(point t)
{
    point temp;
    if(t.x+t.y>=b)
    {
        temp.y=b;
        temp.x=t.x+t.y-b;
    }
    else
    {
        temp.y=t.x+t.y;
        temp.x=0;
    }
    temp.step=t.step+1;
    return temp;
}
point pour2(point t)
{
    point temp;
    if(t.x+t.y>=a)
    {
        temp.x=a;
        temp.y=t.x+t.y-a;
    }
    else
    {
        temp.x=t.x+t.y;
        temp.y=0;
    }
    temp.step=t.step+1;
    return temp;
}
int main()
{
    queue<point> q;
    while(scanf("%d%d%d",&a,&b,&c)!=EOF)
    {
        memset(map,0,sizeof(map));
        memset(opera,0,sizeof(opera));
        bool p=false;
        point p1;
        p1.x=0;
        p1.y=0;
        p1.step=0;
        q.push(p1);
        map[0][0]=true;
        while(!q.empty())
        {
            point temp1=q.front();
            q.pop();
            if(temp1.x==c||temp1.y==c)
            {
                p=true;
                printf("%d\n",temp1.step);
                stack<int> s;
                point temp;
                temp.x=temp1.x;
                temp.y=temp1.y;
                while(temp.x||temp.y)
                {
                    s.push(opera[temp.x][temp.y].oper);
                    int t1=temp.x;
                    int t2=temp.y;
                    temp.x=opera[t1][t2].fx;
                    temp.y=opera[t1][t2].fy;
                }
                while(!s.empty())
                {
                    int temp2=s.top();
                    s.pop();
                    printf("%s\n",op[temp2]);
                }
                break;
            }
            point temp[6];
            temp[0]=fill1(temp1);
            temp[1]=fill2(temp1);
            temp[2]=drop1(temp1);
            temp[3]=drop2(temp1);
            temp[4]=pour1(temp1);
            temp[5]=pour2(temp1);
            for(int i=0;i<6;i++)
            {
                if(!map[temp[i].x][temp[i].y])
                {
                    opera[temp[i].x][temp[i].y].fx=temp1.x;
                    opera[temp[i].x][temp[i].y].fy=temp1.y;
                    opera[temp[i].x][temp[i].y].oper=i;
                    map[temp[i].x][temp[i].y]=true;
                    q.push(temp[i]);
                }
            }
        }
        if(!p)
        printf("impossible\n");
        while(!q.empty())
        q.pop();
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator