题意分析

题目要求使用给定数量的不同长度管道（$L_1, L_2, \dots, L_k$）连接两点 $(x1, y1)$ 和 $(x2, y2)$。管道只能沿水平或垂直方向铺设，且必须形成直线或直角转弯。目标是找到最少管道数量的连接方案，若无法连接则返回 $-1$。

关键约束：

1. 管道方向限制：仅东-西（水平）或北-南（垂直）。
2. 转弯限制：必须为 $90^\circ$ 直角。
3. 管道数量限制：每种长度 $L_i$ 的数量为 $C_i$（$1 \leq C_i \leq 10$）。

解题思路

1. 问题分解：

   • 将连接问题分解为水平方向和垂直方向的独立子问题。
   • 水平距离需满足：$\sum c_i^h L_i = |x2 - x1|$，其中 $c_i^h$ 为水平方向使用的管道数量。
   • 垂直距离需满足：$\sum c_i^v L_i = |y2 - y1|$，其中 $c_i^v$ 为垂直方向使用的管道数量。

2. 暴力搜索：

   • 对每个方向（水平/垂直），枚举所有可能的管道组合：
     • 对于每种长度 $L_i$，尝试使用 $-C_i$ 到 $C_i$ 的数量（负值表示反向铺设）。
     • 检查组合是否满足距离条件：$\left| \sum c_i L_i \right| = \text{目标距离}$。
   • 记录满足条件的最小管道总数 $\sum (|c_i^h| + |c_i^v|)$。

3. 结果合并：

   • 若水平和垂直方向均找到可行解，则总管道数为两者之和。
   • 若任一方向无解，则返回 $-1$。

关键公式

1. 距离条件：$$\left| \sum_{i=1}^k c_i^h L_i \right| = |x2 - x1|, \quad \left| \sum_{i=1}^k c_i^v L_i \right| = |y2 - y1| $$
2. 管道总数：$$\text{Total} = \sum_{i=1}^k \left( |c_i^h| + |c_i^v| \right) $$

参考代码

#include <stdio.h>
 
#define  abs(x) ((x)>0?(x):-(x))
#define  max_num 0xffff
 
int cnt;
int l[4],c[4],buffer[4];
 
void search(int start,int end,int k);
int main()
{
	int x1,y1,x2,y2,k;
	int i,j,result;
 
	//freopen("test.txt","r",stdin);
 
    while(scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&k)!=EOF)
	{
		cnt=max_num;
		result=0;
		for(i=0;i<k;i++)
			c[i]=buffer[i]=0;
 
		for(i=0;i<k;i++)
			scanf("%d",&l[i]);
		for(i=0;i<k;i++)
			scanf("%d",&c[i]);
 
		search(x1,x2,k);
		if(cnt!=max_num)
		{
			result=cnt;
			cnt=max_num;
			for(i=0;i<k;i++)
				c[i]=buffer[i];
			search(y1,y2,k);
		}
 
		if(cnt!=max_num)
		   printf("%d\n",cnt+result);
		else
			printf("-1\n");
	}
	return 0;
}
 
void search(int start,int end,int k)
{
	int c1,c2,c3,c4;
	int temp,num;
 
	for(c1=-1*c[0];c1<=c[0];c1++)
		for(c2=-1*c[1];c2<=c[1];c2++)
			for(c3=-1*c[2];c3<=c[2];c3++)
				for(c4=-1*c[3];c4<=c[3];c4++)
				{
					temp=c1*l[0]+c2*l[1]+c3*l[2]+c4*l[3];
					if(abs(temp)==abs(end-start))
					{
						num=abs(c1)+abs(c2)+abs(c3)+abs(c4);
						if(num<cnt)
						{
							buffer[0]=c[0]-abs(c1);
							buffer[1]=c[1]-abs(c2);
							buffer[2]=c[2]-abs(c3);
							buffer[3]=c[3]-abs(c4);
							cnt=num;
						}
					}
				}
}