《猜图游戏》解题报告.doc

作者声明：此题所附程序，深搜是正确的，会输出所有解。简单推理程序有误。猜图游戏解题报告By sx349 【摘要】核心算法思想：深搜/数学推理主要数据结构：其他辅助知识：时间复杂度：（深搜，显然在强剪枝下常数极小）/（推理，常数也很小）空间复杂度：（常数极小）【题目大意】给定一系列规则和一系列数据，根据规则通过简单推理还原图像。（“简单推理”的定义为，仅考虑某一行（列）的信息以及该行（列）中已知的方块的颜色，推理出该行（列）中更多方块的颜色。）【算法分析】尽管一开始就看到了简单推理这句话，但是一开始并没有想到有效利用这一条件的方法，于是先考虑到用深搜的做法，配合强剪枝来解决。显然，深搜也有好几种做法，可以先搜索行，也可以先搜索列：（以搜索行为例）假设我们搜索到第I行：对每一列维护一个表，搜索到第I行的第J个格子，将这一个各自的状态加入这个表，并且对这个列的表与这个列的状态进行比对。这是一个很普遍的剪枝，显然，这个剪枝的关键在于如何维护这个表。因为这个表中有三种状态：填0（代表白格），填1（代表黑格），以及填-1（代表未确定）。在一开始考虑的时候，我先把所有已经确定的行和列都填好，因此就必须把-1和0区别开来，但是为了接替方便，最后还是将这些已经确定的行作为搜索时的小剪枝，而避免了-1和0的区分，因此，表的状态就只要用一个布尔数组来判断一下就行了。但是布尔数组每次的判断还是要的复杂度，在深搜的过程中如果每一步都判断，那么就必然会超时。因此需要有更好的方法维护这个表。显然，每一列所要求的数字排列是有序的，那么，对于每一列我们都可以用两个数字M，N来表示当前该列的状态，即已经判断了该列的前M个数，并且第M+1个数已经检查了N格（显然N是小于第M+1个数的）。如果当前我们判断这一格是白格，那么判断之前的状态中N是否等于第M+1个数，如果等于，则M加上1，N归零，否则如果小于，则显然不可行，回溯；如果当前我们判断这一个是黑格，那么判断之前的状态中N+1是否超过第M+1个数，如果超过，那么不可行，如果不超过，那么N加上1；当判断完整张表之后，相当于在整张表之下全部添加一列白格，在对每一列进行判断。这样每次的判断复杂度就只有了。那么如何来搜索某一行的状态呢？我们用J，K两个数来表示我们搜索到这一行中的第J-1个空当，且这个空当的长为K。当然，在这里也可以搜索黑格，但是搜索空当的优势在于我们可以在每一行之前和之后都添加一个白格，这样就可以确定空当的开始和结束，而黑格就无法这样做了。搜索空当之后，将空当中的每一个白格都进行一次判断，然后对这个空档之后的一段黑格再逐个进行判断。但是我们又面临了这样一个问题：如何在退出当前层回溯时恢复数据呢？因为层数过深（理论最高900层），所以无论是值参还是局部变量都会成为累赘（毕竟系统栈不深）。因此，我又另开了一个数组，来记录每一步的推理结果。至此，深搜的算法已经大体完成，基本上20*20的数据可以秒杀并且输出所有解，暂时因为没有30*30的数据来进行极限测试，但是由于题述中说是保证唯一解，因此应该能够在时限内得到这一组解。经过与张若愚的讨论和借鉴，我又重新开始研究了简单推理的办法。（还是以行为例）显然，正如我上面所提到过的，有些行和列是可以直接确定下来的。那么，这些行和列已经确定的格子就相当于我们的初始数据。建立一个队列，将这些已经确定的格子加入这个队列，然后进行如下的操作。首先是预处理，对于每一行（或列），我们可以算出所有它可能有的排列。假设我们已经根据第I行的数字，得到了第I行的所有排列，将它们列成一张表。从队列中取出某个确定的格子，将它所在的行（或列，取决于这个格子之前是由行的分析判定还是由列的分析判定的），这样，除了我们已经确定的几个格子之外，有可能在所有的排列中，某一格始终为白格（或黑格），那么马上就可以判定这一格是白格，然后将这一判断入队，重复这一过程。显然，这完全符合上述“简单推理”的定义：仅考虑某一行（列）的信息以及该行（列）中已知的方块的颜色，推理出该行（列）中更多方块的颜色。而且，如果是做为手工笔算小数据的方法，显然是很好的（尤其是这种描述很符合思维习惯）。但是，如何在电脑上实现这一过程呢？我们再次建表，不过，这一次不是建一张，而是对每一行都建两张表，其中横里是这一行的每一个格子位置，竖里是这一行的每一种排列方式。对于横里和竖里的开头都建一个Head。其中，前一张表中的每一个结点（除了Head之外），都是判断中的当前行的可能排列中黑格的位置，后一张表则为白格的位置。这样，我们就可以很轻松的判断某一个是否在所有排列中保持同样的性质了：如果黑格表中某一列的Head直接指向NIL，则这一列必然都是代表白格，反之，白格表中同样的情况下，这一列必然都是代表黑格。而删除的时候，也只用从确定列的Head开始，每往下走到一个就删除一个。在做这两张表的时候，要注意其同步性，在删除时要同步删除，否则可能会导致两边出现误差的情况。而且从上述的描述中也可开出来，这张表的建法应该是双向十字链表，不仅能够节约空间，而且删除操作也极为方便（尽管编程复杂度可能较高，但是放弃链表而采用数组模拟链表会导致内存直接爆掉，因为总的内存开到最大基本上无法预估）。【心得体会】这道题是我最先开始研究的一道题，也许是因为我曾经玩过这个游戏的缘故吧。张若愚神牛给了我莫大的帮助，包括测试数据（在一开始我的程序还跑不出正确答案的时候）以及帮助我解决了推理的做法，当然也包括顺便地把我手机中与此相同的一款游戏打通全关（但是还是没有30*30的数据，而且很多都是多解）。这道题也应该是我有史以来编的最长的程序了，但是这其中经过了很漫长的调试，才最终得到了不错的结果。相信有了这一次的经验和起步，对我未来编写这种复杂程序将会有更大的帮助吧。【附录】 2006选拔赛第三轮第一试 猜图游戏 ederu.pas/c/cpp 输入文件名：ederu.in 时间限制：2S 输出文件名：ederu.out【题目描述】 有一个游戏是这样的。有一幅由黑白小方块组成的矩形图画。已知该图画的每一行（列）中连续出现的黑色方块的数目，要求你根据这些信息推理出该图画中的每一个小方块的颜色。例如在以下的图的例子中，第一行的数字是2 1 1，表示在第一行中连续出现的黑色方块有三组，从左到右依此是两个、一个、一个黑色方块。 可以保证的是在符合这些条件的情况下，答案的图画是唯一确定的。这里，为了对问题作一些简化，有另一个条件，就是结果的图画一定可以从零开始通过若干次的“简单推理”的步骤来得到。“简单推理”的定义为，仅考虑某一行（列）的信息以及该行（列）中已知的方块的颜色，推理出该行（列）中更多方块的颜色。下面是两个简单推理的例子。（图中白色方块表示未知的方块，中间有点的方块以及全黑的方块分别表示推理出一定是白色或黑色的方块）。例：从可以推理出例：从可以推理出【输入】 输入数据的第一行包含两个整数X Y，分别是图画的行数和列数（1 X, Y 30）。 接下来的X行分别描述了从上到下每一行中的黑方块的信息。每一行的格式为Si Xi,1 Xi,2 . Xi,Si。其中Si为第i行中连续的黑方块的组数。Xi,1 Xi,2 . Xi,Si分别为每一组中黑方块的数目。再接下来的Y行分别描述了从左到右每一列中的黑方块的信息。每一行的格式为Ti Yi,1 Yi,2 . Yi,Ti。其中Ti为第i列中连续的黑方块的组数。Yi,1 Yi,2 . Yi,Ti分别为每一组中黑方块的数目。【输出】 输出推理出的图画。即，输出X行，每行输出2Y列。其中，用连续的两个#号表示黑方块，用连续的两个点表示白方块。【样例输入输出】ederu.inederu.out10 103 2 1 11 71 62 1 13 3 1 13 1 1 12 3 12 2 22 4 11 42 1 13 1 1 21 72 2 33 3 2 21 31 21 42 2 42 2 2.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.【源程序清单】深搜: $m 1000000const maxn=31; maxm=31;type point=node; node=record ch:array0.1of point; f:point; end;var a,b,b1:array0.maxnof point; c,d,s:array0.maxmof longint; f:array0.maxmof boolean; t,u:array0.maxm,0.maxnof longint; ans:array0.maxn,0.maxmof boolean; n,m:longint; tt:longint;procedure build(flag,t,k,res:longint);var i,j,u:longint; p,q:point;begin if t=c0+1 then begin fillchar(f,sizeof(f),0); for i:=1 to c0 do for j:=di to di+ci-1 do fj:=true; p:=aflag; for i:=1 to m do begin u:=ord(fi); if p.chu=nil then begin new(q); q.ch0:=nil; q.ch1:=nil; q.f:=p; p.chu:=q; end; p:=p.chu; end; exit; end; for i:=k to m-res+2 do begin dt:=i; build(flag,t+1,i+ct+1,res-ct-1); end;end;procedure init;var i,j,k,l:longint;begin readln(n,m); for i:=1 to m do begin new(ai); ai.ch0:=nil; ai.ch1:=nil; end; for i:=1 to n do begin read(c0); l:=0; for j:=1 to c0 do begin read(cj); inc(l,cj+1); end; build(i,1,1,l); end; for i:=1 to m do begin read(ti,0); for j:=1 to ti,0 do begin read(ti,j); inc(si,ti,j+1); end; end;end;procedure print;var i,j:longint;begin inc(tt); writeln(No.,tt,:); fillchar(ans,sizeof(ans),0); for i:=1 to n do b1i:=bi; for i:=m downto 1 do for j:=1 to n do begin ansj,i:=bj=bj.f.ch1; bj:=bj.f; end; for i:=1 to n do begin for j:=1 to m do if ansi,j then write(#) else write(.); writeln; end; writeln; for i:=1 to n do bi:=b1i;end;procedure search(flag,x,k,res:longint);var i,j:longint; able:boolean;begin if flag=m+1 then begin print; exit;/ close(input); close(output);/ halt; end; if x=tflag,0+1 then begin fillchar(f,sizeof(f),0); for i:=1 to tflag,0 do for j:=uflag,i to uflag,i+tflag,i-1 do fj:=true; able:=true; for i:=1 to n do begin if bi.chord(fi)=nil then begin able:=false; break; end; bi:=bi.chord(fi); end; if not able then for i:=1 to i-1 do bi:=bi.f else begin search(flag+1,1,1,sflag+1); for i:=1 to n do bi:=bi.f; end; exit; end; for i:=k to n-res+2 do begin uflag,x:=i; search(flag,x+1,i+tflag,x+1,res-tflag,x-1); end;end;procedure work;var i:longint;begin for i:=1 to n do bi:=ai; search(1,1,1,s1);end;begin /assign(input,1.txt); reset(input); /assign(output,2.txt); rewrite(output); init; work; close(input); close(output);end.推理:const maxstate=10001;type node=record l,r,u,d:longint; end; point=record x,y,f:longint; end; state=array0.maxstate,0.31of node;var a:array0.1,0.31,0.1of state; b,c:array0.31of longint; q:array0.901of point; f:array0.31,0.31of boolean; t:array0.31of boolean; n,m,tt:longint; l,r:longint; map:array0.30,0.30of longint; max:longint;procedure add0(var s:state);var i,k,l:longint;begin inc(s0,0.d); k:=s0,0.d; if kmax then max:=k; l:=0; for i:=1 to tt do if ti then begin sk,i.l:=l; sk,l.r:=i; l:=i; ssmaxstate,i.d,i.d:=k; sk,i.u:=smaxstate,i.d; smaxstate,i.d:=k; end;end;procedure add1(var s:state);var i,k,l:longint;begin inc(s0,0.d); k:=s0,0.d; if kmax then max:=k; l:=0; for i:=1 to tt do if not ti then begin sk,i.l:=l; sk,l.r:=i; l:=i; ssmaxstate,i.d,i.d:=k; sk,i.u:=smaxstate,i.d; smaxstate,i.d:=k; end;end;procedure build(flag,row,now,start,rest:longint);var i,j,k,l:longint;begin if now=c0+1 then begin fillchar(t,sizeof(t),0); for i:=1 to c0 do for j:=bi to bi+ci-1 do tj:=true; if (b1=4)and(b2=7)and(b3=9) then begin flag:=flag; end; add0(aflag,row,0); add1(aflag,row,1); exit; end; for i:=start to rest do begin bnow:=i; build(flag,row,now+1,i+cnow+1,rest+cnow+1); end;end;procedure init;var i,j,t:longint;begin readln(n,m); tt:=m; for i:=1 to n do begin t:=0; read(c0); for j:=1 to c0 do begin read(cj); inc(t,cj+1); end; build(0,i,1,1,m-t+2); end; tt:=n; for i:=1 to m do begin t:=0; read(c0); for j:=1 to c0 do begin read(cj); inc(t,cj+1); end; build(1,i,1,1,n-t+2); end; readln;end;procedure addpoint(x,y,flag:longint);begin if fx,y then exit; inc(r); qr.x:=x; qr.y:=y; qr.f:=flag; fx,y:=true;end;procedure disposeline(var s:state; t,x,flag,mark:longint);var i:longint;begin i:=st,0.r; while i0 do begin sst,i.u,i.d:=st,i.d; sst,i.d,i.u:=st,i.u; if s0,i.d=0 then if mark=0 then addpoint(x,i,flag) else addpoint(i,x,flag); i:=st,i.r; end;end;procedure deletestate(var s:state; t,x,flag,mark:longint);var i:longint;begin i:=s0,t.d; while i0 do begin disposeline(amark,x,flag,i,x,1-flag,mark); disposeline(amark,x,1-flag,i,x,flag,mark); i:=si,t.d; end;end;procedure work;var i,j:longint;begin l:=1; r:=0; for i:=1 to n do for j:=1 to m do begin if a0,i,00,j.d=0 then addpoint(i,j,1); if a0,i,10,j.d=0 then addpoint(i,j,0); if a1,j,00,i.d=0 then addpoint(i,j,1); if a1,j,10,i.d=0 then addpoint(i,j,0); end; while l=r do begin mapql.x,ql.y:=ql.f; deletestate(a0,ql.x,1-ql.f,ql.y,ql.x,1-ql.f,0); deletestate(a1,ql.y,1-ql.f,ql.x,ql.y,1-ql.f,1); inc(l); end;end;procedure print;var i,j:longint;begin for i:=1 to n do begin for j:=1 to m do if mapi,j=1 then write(.) else write(#); writeln; end;end;begin /assign(input,1.txt); reset(input); /assign(output,3.txt); rewrite(output); init; work; print; writeln(max); close(output);end.