老汉分田——解题报告
发表时间：2010-07-09 11:22:58 浏览(2661) 评论(1)
【题目描述】
王老汉有一块正方形的田地，它们被均匀的分割成2N*2N块。最左上角的田块的左上角的坐标为(0,0)，
最右下角的田地的右下角坐标为(2N,2N),其中第一个分量用来描述行，第二个分量用来描述列。在某些田块的四个角上可能有水井存在，每个水井的位置可以用坐标(a, b)来进行描述，其中0<=a,b<=2N。
他想把这块田地分给他的两个儿子，为了尽量公平，老汉的分田原则是这样的：
1.每个儿子分得的田地数量为2*N^2块，即他们必须均分老汉的田地
2.每个儿子分得的田地都是相互连通的，两块田地互相连通当且就当满足如下定义：
a)如果田地A与田地B之间有一条共同的边，那么他们是连通的
b)如果田地A与田地B连通，田地B与田地C连通，那么田地A与田地C连通
3.任何一口水井都不会被一个儿子所独占，即它周围的田地，不可能同时属于同一个儿子（水井不会出 现在(0,0),(0,2N),(2N,0),(2N,2N)四个顶角）。
4.两个儿子获得的田地的形状是相同的，也就是说将一个儿子获得的田地旋转180度后一定与另一个儿子获 得的田地重合。（这里不考虑水井）
现在你拿到了老汉田地的地图，知道了所有水井的位置，现在老汉希望你帮他计算一下总共有多少种分田方案。注意：如果两种方案通过旋转或者是镜面反射以后切分形状一样，将会被视作不同的方案。
输入
输入的第一行有两个正整数N, M，其中M表示老汉田地上所有水井的数量，接下来的M行，每行有两个整数a，b表示每一水井的坐标。其中 2<=N<=4, 0<=M<=20 。
输出
输出数据仅有一行，表示切分方案数，如果无解，请输出0.
以下是样例中数据的地图
【样例输入】
2 3
1 0
1 1
1 2
【样例输出】
6
【解题思路】
有神牛说可以基于连通性的状态压缩DP，本人很菜不会。这道题用的搜索。
考虑题目的要求，发现合法的分割方式必然是导致分成以中心对称的两块。首先想到枚举哪些格子属于1，哪些格子属于2。然后判断连通性和井，搜索中间要可行性剪枝。但是后来发现这个思路编下去！@#￥%……&
换了一个思路，枚举分界线。分界线经过每个交点最多一次，而且是中心对称的。所以从中心开始搜索，最后判断井是否都在边界上。事实证明这种方法速度惊人。
【我的代码】
var i,j,k,l,m,n,p,q,r,s,t:longint;
zb:array[0..20,1..2] of longint;
a:array[0..8,0..8] of longint;
sel,jing:array[0..8,0..8] of boolean;
ans,mid,dx,dy:longint;
can:boolean;
procedure check;
begin
for i:=1 to m do
if (not sel[zb[i,1],zb[i,2]]) then exit;
inc(ans);
end;
procedure dfs(x,y:longint);
begin
sel[x,y]:=true;
sel[n*2-x,n*2-y]:=true;
if (x=0)or(x=n*2)or(y=0)or(y=n*2) then
begin
check;
sel[x,y]:=false;
sel[n*2-x,n*2-y]:=false;
exit;
end;
if (x>0)and(not sel[x-1,y]) then dfs(x-1,y);
if (x<n*2)and(not sel[x+1,y]) then dfs(x+1,y);
if (y>0)and(not sel[x,y-1]) then dfs(x,y-1);
if (y<n*2)and(not sel[x,y+1]) then dfs(x,y+1);
sel[x,y]:=false;
sel[n*2-x,n*2-y]:=false;
end;
begin
read(n,m);
for i:=1 to m do
begin
read(zb[i,1],zb[i,2]);
end;
ans:=0;
fillchar(sel,sizeof(sel),false);
sel[n,n]:=true;
dfs(n,n+1);
dfs(n+1,n);
writeln(ans*2);
end.
王老汉有一块正方形的田地，它们被均匀的分割成2N*2N块。最左上角的田块的左上角的坐标为(0,0)，
最右下角的田地的右下角坐标为(2N,2N),其中第一个分量用来描述行，第二个分量用来描述列。在某些田块的四个角上可能有水井存在，每个水井的位置可以用坐标(a, b)来进行描述，其中0<=a,b<=2N。
他想把这块田地分给他的两个儿子，为了尽量公平，老汉的分田原则是这样的：
1.每个儿子分得的田地数量为2*N^2块，即他们必须均分老汉的田地
2.每个儿子分得的田地都是相互连通的，两块田地互相连通当且就当满足如下定义：
a)如果田地A与田地B之间有一条共同的边，那么他们是连通的
b)如果田地A与田地B连通，田地B与田地C连通，那么田地A与田地C连通
3.任何一口水井都不会被一个儿子所独占，即它周围的田地，不可能同时属于同一个儿子（水井不会出 现在(0,0),(0,2N),(2N,0),(2N,2N)四个顶角）。
4.两个儿子获得的田地的形状是相同的，也就是说将一个儿子获得的田地旋转180度后一定与另一个儿子获 得的田地重合。（这里不考虑水井）
现在你拿到了老汉田地的地图，知道了所有水井的位置，现在老汉希望你帮他计算一下总共有多少种分田方案。注意：如果两种方案通过旋转或者是镜面反射以后切分形状一样，将会被视作不同的方案。
输入
输入的第一行有两个正整数N, M，其中M表示老汉田地上所有水井的数量，接下来的M行，每行有两个整数a，b表示每一水井的坐标。其中 2<=N<=4, 0<=M<=20 。
输出
输出数据仅有一行，表示切分方案数，如果无解，请输出0.
以下是样例中数据的地图
【样例输入】
2 3
1 0
1 1
1 2
【样例输出】
6
【解题思路】
有神牛说可以基于连通性的状态压缩DP，本人很菜不会。这道题用的搜索。
考虑题目的要求，发现合法的分割方式必然是导致分成以中心对称的两块。首先想到枚举哪些格子属于1，哪些格子属于2。然后判断连通性和井，搜索中间要可行性剪枝。但是后来发现这个思路编下去！@#￥%……&
换了一个思路，枚举分界线。分界线经过每个交点最多一次，而且是中心对称的。所以从中心开始搜索，最后判断井是否都在边界上。事实证明这种方法速度惊人。
【我的代码】
var i,j,k,l,m,n,p,q,r,s,t:longint;
zb:array[0..20,1..2] of longint;
a:array[0..8,0..8] of longint;
sel,jing:array[0..8,0..8] of boolean;
ans,mid,dx,dy:longint;
can:boolean;
procedure check;
begin
for i:=1 to m do
if (not sel[zb[i,1],zb[i,2]]) then exit;
inc(ans);
end;
procedure dfs(x,y:longint);
begin
sel[x,y]:=true;
sel[n*2-x,n*2-y]:=true;
if (x=0)or(x=n*2)or(y=0)or(y=n*2) then
begin
check;
sel[x,y]:=false;
sel[n*2-x,n*2-y]:=false;
exit;
end;
if (x>0)and(not sel[x-1,y]) then dfs(x-1,y);
if (x<n*2)and(not sel[x+1,y]) then dfs(x+1,y);
if (y>0)and(not sel[x,y-1]) then dfs(x,y-1);
if (y<n*2)and(not sel[x,y+1]) then dfs(x,y+1);
sel[x,y]:=false;
sel[n*2-x,n*2-y]:=false;
end;
begin
read(n,m);
for i:=1 to m do
begin
read(zb[i,1],zb[i,2]);
end;
ans:=0;
fillchar(sel,sizeof(sel),false);
sel[n,n]:=true;
dfs(n,n+1);
dfs(n+1,n);
writeln(ans*2);
end.
网友评论：
 | 1 Guest 于 2010-10-28 21:46:53 说： | 回复 |
|---|---|---|
好(^o^)/~！ |