用户登录:

用户名:
密码:      

文章分类:


最新评论:

userleijiankun 说:膜拜神牛。……
usercss 说:康拓展开和逆康拓展……
usersongrenchu 说:欢迎大家踊……
userAdmin 说:……

老汉分田——解题报告

发表时间:2010-07-09 11:22:58  浏览(1370) 评论(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. 

以下是样例中数据的地图
srcoiblog

【样例输入】 
2 3
1 0
1 1
1 2

【样例输出】 
6

srcoiblog

【解题思路】
  有神牛说可以基于连通性的状态压缩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. 

网友评论:

user1  Guest 于 2010-10-28 21:46:53 说:回复
好(^o^)/~!

Guest 发表评论