奶牛食物解题报告.doc

【问题描述】农夫约翰购买了一处肥沃的矩形牧场，分成M*N(1=M=12; 1=N=12)个格子。他想在那里的一些格子中种植美味的玉米。遗憾的是，有些格子区域的土地是贫瘠的，不能耕种。精明的约翰知道奶牛们进食时不喜欢和别的牛相邻，所以一旦在一个格子中种植玉米，那么他就不会在相邻的格子中种植，即没有两个被选中的格子拥有公共边。他还没有最终确定哪些格子要选择种植玉米。作为一个思想开明的人，农夫约翰希望考虑所有可行的选择格子种植方案。由于太开明，他还考虑一个格子都不选择的种植方案！请帮助农夫约翰确定种植方案总数。【输入格式】第一行：两个用空格分隔的整数M和N。第二行到第M+1行：第i+1行描述牧场第i行每个格子的情况，N个用空格分隔的整数，表示这个格子是否可以种植（1表示肥沃的、适合种植，0表示贫瘠的、不可种植）。【输出格式】一个整数，农夫约翰可选择的方案总数除以 100,000,000 的余数。【样例输入】2 31 1 10 1 0【样例输出】9【样例说明】给可以种植玉米的格子编号：1 2 34只种一个格子的方案有四种(1,2,3或4)，种植两个格子的方案有三种(13,14或34)，种植三个格子的方案有一种(134)，还有一种什么格子都不种，则：4+3+1+1=9。【数据规模】对于30%的数据，N,M=4；对于100%的数据，N,M=12。【分析】把地图存在map中。先来看看对于单独一行来说，哪些状态是可行的。不考虑不能种的地，题目要求状态中不允许存在连续的1，这一要求可以用程序中的impossible函数来判断。经过判断后，将可行的状态存在st数组中。然后DP：fi,j表示在第i行中，状态为j的方案数。枚举第i-1行的状态k。要满足两个条件：1：j和mapi不能冲突，也就是不能有不能种的地。2:k和mapi-1不能冲突。3：j和k不能冲突。在满足这些条件的前提下，有：fi,j := fi,j + fi-1,kCode:const MM=100000000;varn,m,i,j,v:longint;cf:array0.4097,0.4097 of boolean;map:array0.100 of longint;ans:array0.100,0.4097 of longint;st:array0.4097 of longint;a:array0.100,0.100 of longint;function ok(x:longint):boolean;var i:longint;begin for i:=1 to m do if (x and(1 shl i)=2*(x and (1 shl (i-1)and(x and(1 shl i)0) then exit(false); exit(true);end;procedure checkline;var i:longint;begin st0:=0; for i:=0 to 1 shl m-1 do if ok(i) then begin inc(st0); stst0:=i; end;end;function ok2(x,y:longint):boolean;var i:longint;begin for i:=1 to m do if (x and(1 shl(i-1)0)and(x and (1 shl (i-1)=(y and (1 shl(i-1) then exit(false); ok2:=true;end;procedure checkok;var i,j:longint;begin fillchar(cf,sizeof(cf),false); for i:=1 to st0 do for j:=i to st0 do if ok2(sti,stj) then begin cfi,j:=true; cfj,i:=true; end;end;procedure dp;var i,j,k:longint;begin fillchar(ans,sizeof(ans),0); ans0,1:=1; map0:=1 shl m-1; for i:=1 to n do for j:=1 to st0 do if (stj or mapi)mapi then ansi,j:=-1 else for k:=1 to st0 do if (ansi-1,k-1)and(cfj,k) then ansi,j:=(ansi,j+ansi-1,k) mod MM;end;procedure print;var opt,i:longint;begin opt:=0; for i:=1 to st0 do if ansn,i-1 then opt:=(opt+ansn,i) mod MM; writeln(opt);end;beginassign(input,cowfood.in);reset(input);readln(n,m);for i:=1 to n dobegi