Water pipe

Time Limit: 3000MS Memory Limit: 65536K

Total Submissions: 2265 Accepted: 602

Description

The Eastowner city is perpetually haunted with water supply shortages, so in order to remedy this problem a new water-pipe has been built. Builders started the pipe from both ends simultaneously, and after some hard work both halves were connected. Well, almost. First half of pipe ended at a point (x1, y1), and the second half – at (x2, y2). Unfortunately only few pipe segments of different length were left. Moreover, due to the peculiarities of local technology the pipes can only be put in either north-south or east-west direction, and be connected to form a straight line or 90 degree turn. You program must, given L1, L2, … Lk – lengths of pipe segments available and C1, C2, … Ck – number of segments of each length, construct a water pipe connecting given points, or declare that it is impossible. Program must output the minimum required number of segments.

Constraints

1 <= k <= 4, 1 <= xi, yi, Li <= 1000, 1 <= Ci <= 10

Input

Input contains integers x1 y1 x2 y2 k followed by 2k integers L1 L2 … Lk C1 C2 … Ck

Output

Output must contain a single integer – the number of required segments, or −1 if the connection is impossible.

Sample Input

20 10 60 50 2 70 30 2 2

Sample Output

4

Source

Northeastern Europe 2003, Far-Eastern Subregion

题目链接：

题意：

在二维网格上给你起点，终点，与（n《=10）的管子（长度与数量）用最少的管子数完毕路径；

思路：由于管子不能切断。所以“盲目”dfs 长路漫漫。。。

仅仅好迭代加深！

——————–分开计算x。y轴————————–

1.预处理*h数组。计算i状态到终点（单维）的最最短路（估价系统）

for(ans=1;ans<=tot;ans++){if(dfs(a,sx,0,0)) break;}

2.“盲目”dfs（+剪枝）到终点（单维）

剪*

if(hv==-1||hv+dep>ans) return 0;

代码：

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;struct node{    int l,num;}a[11];int n,h1[1010],h2[1010],ans;int tx,ty,sx,sy;int tot;void cal(int *h,int pos){    queue
          
            q;    h[pos]=0;    q.push(pos);    while(!q.empty())    {        pos=q.front();        q.pop();        for(int i=1;i<=n;i++)        {            int nex=pos-a[i].l;            if(nex>0&&h[nex]==-1)            {                h[nex]=h[pos]+1;                q.push(nex);            }            nex+=2*a[i].l;            if(nex<=1000&&h[nex]==-1)            {                h[nex]=h[pos]+1;                q.push(nex);                    }        }    }}bool dfs(node *a,int x,int dep,int id){    int hv;    if(id==0) hv=h1[x];else hv=h2[x];    if(hv==-1||hv+dep>ans) return 0;    if(hv==0)    {        if(id==0) return dfs(a,sy,dep,1);        else return 1;    }    node tmp[10];    for(int i=1;i<=n;i++) tmp[i]=a[i];    for(int i=1;i<=n;i++)    if(tmp[i].num)    {        tmp[i].num--;        int now=x-tmp[i].l;        if(now>0) if(dfs(tmp,now,dep+1,id)) return 1;        now+=2*tmp[i].l;        if(now<=1000) if(dfs(tmp,now,dep+1,id)) return 1;        tmp[i].num++;    }    return 0;}void id_a_star(){    memset(h1,-1,sizeof(h1));    memset(h2,-1,sizeof(h2));    cal(h1,tx);    cal(h2,ty);    for(ans=1;ans<=tot;ans++)    {        if(dfs(a,sx,0,0)) break;    }    if(ans<=tot)    printf("%d\n",ans);    else printf("-1\n");}int main(){    scanf("%d%d%d%d%d",&sx,&sy,&tx,&ty,&n);    for(int i=1;i<=n;i++) scanf("%d",&a[i].l);    for(int i=1;i<=n;i++)     {        scanf("%d",&a[i].num);        tot+=a[i].num;    }    if(sx==tx&&sy==ty) printf("0\n");    else id_a_star();}