題意是這樣的：
有一堆管子，長度為k，數(shù)量為n，然后起點(diǎn)為x1,y1,終點(diǎn)為x2,y2，管道只能水平、垂直放置，問最少需要的管子數(shù)量。如果不可能，輸出-1
這題由于狀態(tài)太大，采取一般的BFS肯定要爆時間，所以，還是用IDA*。首先，觀察到x方向和y方向可以獨(dú)立來處理，下限函數(shù)可以取為沒有數(shù)量限制時從a到b需要的最少管道數(shù)，這個可以通過BFS來解決，復(fù)雜度為O(n)。
不多說，貼代碼
1
Source Code
2# include <cstdio>
3# include <cstring>
4# include <queue>
5using namespace std;
6int c[5],l[5],n,res=0xfffffff;
7int x1,y1,x2,y2;
8int referx[1001],refery[1001];
9queue<int> q;
10bool solve(int pos,int len,bool type)
11
{
12
if(!type)
13
{
14 if(referx[pos]==-1||len+referx[pos]>res) return false;
15 if(pos==x2)
16 {
17 return solve(y1,len,1);
18
}
19 for(int i=1;i<=n;i++)
20 if(c[i])
21 {
22 if(x2<pos)
23 {
24 if(pos-l[i]>=1)
25 {
26 c[i]--;
27 if(solve(pos-l[i],len+1,0)) return true;;
28 c[i]++;
29 }
30 if(pos+l[i]<=1000)
31 {
32 c[i]--;
33 if(solve(pos+l[i],len+1,0)) return true;
34 c[i]++;
35 }
36 }
37 else
38 {
39 if(pos+l[i]<=1000)
40 {
41 c[i]--;
42 if(solve(pos+l[i],len+1,0)) return true;
43 c[i]++;
44 }
45 if(pos-l[i]>=1)
46 {
47 c[i]--;
48 if(solve(pos-l[i],len+1,0)) return true;;
49 c[i]++;
50 }
51 }
52 }
53 }
54 else
55 {
56 if(refery[pos]==-1||len+refery[pos]>res) return false;
57 if(pos==y2)
58 {
59 return true;
60 }
61 for(int i=1;i<=n;i++)
62 if(c[i])
63 {
64 if(y2<pos)
65 {
66 if(pos-l[i]>=1)
67 {
68 c[i]--;
69 if(solve(pos-l[i],len+1,1)) return true;
70 c[i]++;
71 }
72 if(pos+l[i]<=1000)
73 {
74 c[i]--;
75 if(solve(pos+l[i],len+1,1)) return true;
76 c[i]++;
77 }
78 }
79 else
80 {
81 if(pos+l[i]<=1000)
82 {
83 c[i]--;
84 if(solve(pos+l[i],len+1,1)) return true;
85 c[i]++;
86 }
87 if(pos-l[i]>=1)
88 {
89 c[i]--;
90 if(solve(pos-l[i],len+1,1)) return true;
91 c[i]++;
92 }
93 }
94 }
95 }
96 return false;
97
}
98void cal(int refer[],int pos)
99{
100 refer[pos]=0;
101 q.push(pos);
102 while(!q.empty())
103 {
104 pos=q.front();
105 q.pop();
106 for(int i=1;i<=n;i++)
107 {
108 if(pos-l[i]>=1&&refer[pos-l[i]]==-1)
109 {
110 refer[pos-l[i]]=refer[pos]+1;
111 q.push(pos-l[i]);
112 }
113 if(pos+l[i]<=1000&&refer[pos+l[i]]==-1)
114 {
115 refer[pos+l[i]]=refer[pos]+1;
116 q.push(pos+l[i]);
117 }
118 }
119 }
120}
121int main()
122{
123 int total=0;
124 scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&n);
125 for(int i=1;i<=n;i++)
126 scanf("%d",l+i);
127 for(int i=1;i<=n;i++)
128 {
129 scanf("%d",c+i);
130 total+=c[i];
131 }
132 memset(referx,-1,sizeof(referx));
133 memset(refery,-1,sizeof(refery));
134 cal(referx,x2);
135 cal(refery,y2);
136 for(res=0;res<=total;res++)
137 if(solve(x1,0,0)) break;
138 if(res==total+1) printf("-1\n");
139 else printf("%d\n",res);
140 // system("pause");
141 return 0;
142}
143
144