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

可恶,居然有impossible……终于a了

Posted by lmy199433 at 2011-10-18 21:00:49 on Problem 3414
#include<stdio.h>
const int N=201;
int n,m,e,a[2],h,t;
bool b[N][N];
struct queue
{
  int a[2],pre,step;
  short k;
  bool v()
  {return b[a[0]][a[1]];}
  void visit()
  {b[a[0]][a[1]]=1;}
}l[N*N];
void add(queue &x,int pre,int k)
{
  if(x.v())return;
  x.visit();
  x.pre=pre;
  x.k=k;
  x.step=l[pre].step+1;
  l[++t]=x;
}
void out(queue x)
{
  if(x.k==0)return;
  out(l[x.pre]);
  if(x.k%3==1)printf("DROP(%d)\n",x.k/3+1);
  if(x.k%3==2)printf("FILL(%d)\n",x.k/3+1);
  if(x.k%3==0)printf("POUR(%d,%d)\n",x.k/3,1+(x.k&1));
}
int main()
{
  freopen("poj3414.in","r",stdin);
  freopen("poj3414.out","w",stdout);
  scanf("%d%d%d",&a[0],&a[1],&e);
  t=-1;
  add(l[0],0,0);
  l[0].step=0;
  for(;h<=t;h++)
  {
    queue x=l[h];
    if(x.a[0]==e||x.a[1]==e)
    {
      printf("%d\n",x.step);
      out(x);
      return 0;
    }
    for(int i=0;i<2;i++)
    {
      x=l[h];
      x.a[i]=0;
      add(x,h,1+i*3);
      x=l[h];
      x.a[i]=a[i];
      add(x,h,2+i*3);
      x=l[h];
      x.a[i+1&1]+=x.a[i];
      if(x.a[i+1&1]>a[i+1&1])
      {
        x.a[i]=x.a[i+1&1]-a[i+1&1];
        x.a[i+1&1]=a[i+1&1];
      }else x.a[i]=0;
      add(x,h,3+i*3);
    }
  }
  printf("impossible\n");
}

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