首页 > 代码库 > XJOI2061围栏问题【深度优先搜索】

XJOI2061围栏问题【深度优先搜索】

2024-09-25 10:22:01   215人阅读

围栏问题

在一片草原上，有n只兔子无忧无虑地生活着。这片草原可以划分成m×m的方阵。每个方格内最多有一只兔子。
一位饲养员负责喂养这些兔子。为了方便，她需要用篱笆建造最多k座围栏，将草原上的兔子全部围起来。
围栏需要满足以下条件：
（1）必须沿着网格线建造；
（2）每座围栏是一个不与自身重叠或相交的封闭回路；
（3）各座围栏之间互相不重叠、不相交；
（4）一座围栏不能被围在另一座围栏里面。
请你帮助饲养员计算一下围栏总长度的最小值。

输入格式：

输入文件名为fence.in
输入第1行为三个整数m，k，n。
接下来n行每行为一对正整数x，y，表示第x行第y列的方格中有一只兔子。

输出格式：

输出文件名为fence.out
输出仅1行，为一个正整数，表示围栏总长度的最小值。

样例输入：

样例1
6 1 4
1 3
4 2
4 4
6 4
样例2
6 2 4
1 3
4 2
4 4
6 4

样例输出：

样例1
18
样例2
16

数据范围：

对于10%的数据，k=1；
对于10%~30%的数据，k=2；
对于30%~60%的数据，n≤10；
对于100%的数据，1≤k≤n≤16，m≤1,000。

时间限制：

1S

空间限制：

128M
考虑到围栏数和兔子数如此之少，可以暴搜，枚举一只兔子加入前面那个围栏，或是自建围栏.
至于相交与包围的问题不用考虑，这两种情况做出来一定不是最优解.
 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 const int N=17;
 5 int xx[N],yy[N],n,m,k;
 6 int lx[N],ly[N],rx[N],ry[N],ans=2e9;
 7 inline void dfs(int x,int y,int z)
 8 {
 9     if(z>ans) return;
10     if(x>n)
11     {
12         ans=z;
13         return;
14     }
15     if(y<k)
16     {
17         rx[y+1]=lx[y+1]=xx[x];
18         ry[y+1]=ly[y+1]=yy[x];
19         dfs(x+1,y+1,z+4);
20         rx[y+1]=lx[y+1]=0;
21         ry[y+1]=ly[y+1]=0;
22     }
23     int ax,ay,bx,by,nz;
24     for(int i=1;i<=y;i++)
25     {
26         ax=lx[i];
27         ay=ly[i];
28         bx=rx[i];
29         by=ry[i];
30         nz=z-2*((bx-ax+1)+(by-ay+1));
31         lx[i]=min(xx[x],lx[i]);
32         rx[i]=max(xx[x],rx[i]);
33         ly[i]=min(yy[x],ly[i]);
34         ry[i]=max(yy[x],ry[i]);
35         nz+=2*((rx[i]-lx[i]+1)+(ry[i]-ly[i]+1));
36         dfs(x+1,y,nz);
37         lx[i]=ax;
38         ly[i]=ay;
39         rx[i]=bx;
40         ry[i]=by;
41     }
42 }
43 int main()
44 {
45     scanf("%d%d%d",&m,&k,&n);
46     for(int i=1;i<=n;i++) scanf("%d%d",&xx[i],&yy[i]);
47     dfs(1,0,0);
48     printf("%d\n",ans);
49     return 0;
50 }

 

XJOI2061围栏问题【深度优先搜索】


联系
我们