Source Code

Problem: 2331  User: yzhw 
Memory: 600K  Time: 47MS 
Language: G++  Result: Accepted 

Source Code 
# include <cstdio>
# include <cstring>
# include <queue>
using namespace std;
int c[5],l[5],n,res=0xfffffff;
int x1,y1,x2,y2;
int referx[1001],refery[1001];
queue<int> q;
bool solve(int pos,int len,bool type)
{
   if(!type)
   {
        if(referx[pos]==-1||len+referx[pos]>res) return false;
        if(pos==x2) 
        {
            return solve(y1,len,1);
        }
        for(int i=1;i<=n;i++)
          if(c[i])
          { 
            if(x2<pos)
            {
             if(pos-l[i]>=1)
             {
                c[i]--;
                if(solve(pos-l[i],len+1,0)) return true;;
                c[i]++;
             }
             if(pos+l[i]<=1000)
             {
                c[i]--;
                if(solve(pos+l[i],len+1,0)) return true;
                c[i]++;
             }
            }
            else
            {
             if(pos+l[i]<=1000)
             {
                c[i]--;
                if(solve(pos+l[i],len+1,0)) return true;
                c[i]++;
             }
             if(pos-l[i]>=1)
             {
                c[i]--;
                if(solve(pos-l[i],len+1,0)) return true;;
                c[i]++;
             }
            }
          }
   }
   else
   {
        if(refery[pos]==-1||len+refery[pos]>res) return false;
        if(pos==y2) 
        {
            return true;
        }
        for(int i=1;i<=n;i++)
          if(c[i])
          { 
            if(y2<pos)
            {
             if(pos-l[i]>=1)
             {
                c[i]--;
                if(solve(pos-l[i],len+1,1)) return true;
                c[i]++;
             }
             if(pos+l[i]<=1000)
             {
                c[i]--;
                if(solve(pos+l[i],len+1,1)) return true;
                c[i]++;
             }
            }
            else
            {
             if(pos+l[i]<=1000)
             {
                c[i]--;
                if(solve(pos+l[i],len+1,1)) return true;
                c[i]++;
             }
             if(pos-l[i]>=1)
             {
                c[i]--;
                if(solve(pos-l[i],len+1,1)) return true;
                c[i]++;
             }
            }
          }
   }
   return false;
}
void cal(int refer[],int pos)
{
    refer[pos]=0;
    q.push(pos);
    while(!q.empty())
    {
       pos=q.front();
       q.pop();
       for(int i=1;i<=n;i++)
       {
         if(pos-l[i]>=1&&refer[pos-l[i]]==-1)
          {
              refer[pos-l[i]]=refer[pos]+1;
              q.push(pos-l[i]);
          }
         if(pos+l[i]<=1000&&refer[pos+l[i]]==-1)
          {
              refer[pos+l[i]]=refer[pos]+1;
              q.push(pos+l[i]);
          }
       }
    }
}
int main()
{
    int total=0;
    scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&n);
    for(int i=1;i<=n;i++)
       scanf("%d",l+i);
    for(int i=1;i<=n;i++)
    {
       scanf("%d",c+i);
       total+=c[i];
    }
    memset(referx,-1,sizeof(referx));
    memset(refery,-1,sizeof(refery));
    cal(referx,x2);
    cal(refery,y2);
    for(res=0;res<=total;res++)
       if(solve(x1,0,0)) break;
    if(res==total+1) printf("-1\n");
    else printf("%d\n",res);
 //   system("pause");
    return 0;
}