本文主要是介绍搜索 MAYAN，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题：NOIP 2011 MAYAN
类型：搜索 （小剪枝），不是很难
program mayan;
type
byte=integer;state=array[1..5,1..7]of byte;oper=objecta,b,c:array[1..5]of byte;procedure push(d,x,y,t:byte);procedure print;end;
var limit:byte; a:state; o:oper;
procedure oper.push(d,x,y,t:byte);
begina[d]:=x; b[d]:=y; c[d]:=t;
end;
procedure oper.print; var i:byte;
beginfor i:=1 to limit dowriteln(a[i]-1,' ',b[i]-1,' ',2-c[i]);close(input);close(output);halt;
end;var mark:array[1..5,1..7]of boolean;
function drop(var a:state;var tot:byte):boolean; var i,j:byte;
beginfillchar(mark,sizeof(mark),0); drop:=false;for i:=3 to 5 dofor j:=1 to 7 doif a[i][j]>0 thenif (a[i][j]=a[i-1][j])and(a[i][j]=a[i-2][j]) then beginmark[i][j]:=true;mark[i-1][j]:=true;mark[i-2][j]:=true;drop:=true;end;for i:=1 to 5 dofor j:=3 to 7 doif a[i][j]>0 thenif (a[i][j]=a[i][j-1])and(a[i][j]=a[i][j-2]) then beginmark[i][j]:=true;mark[i][j-1]:=true;mark[i][j-2]:=true;drop:=true;end;for i:=1 to 5 dofor j:=1 to 7 doif mark[i][j] then begin a[i][j]:=0; dec(tot); end;
end;procedure del(var a:state);
var g:array[1..7]of byte; i,j,t:byte;
beginfor i:=1 to 5 do begint:=0;move(a[i],g,sizeof(g));fillchar(a[i],sizeof(a[i]),0);for j:=1 to 7 do if g[j]>0 then begininc(t); a[i][t]:=g[j];end;end;
end;procedure dfs(const dep:byte; const a:state; const tot:byte);
var tmp:state; tt:byte; i,j:byte;procedure swap(var i,j:byte);var t:byte;begin t:=i; i:=j; j:=t; end;
beginif dep=limit thenif tot=0 then o.print else exit;for i:=1 to 5 dofor j:=1 to 7 do if a[i][j]>0 then beginif i<5 then beginif a[i][j]=a[i+1][j] then continue;move(a,tmp,sizeof(a)); tt:=tot;swap(tmp[i][j],tmp[i+1][j]);del(tmp);while drop(tmp,tt) do del(tmp);o.push(dep+1,i,j,1);dfs(dep+1,tmp,tt);end;if i>1 then beginif a[i][j]=a[i-1][j] then continue;if (a[i-1][j]>0)and(a[i][j]>0) then continue;move(a,tmp,sizeof(a)); tt:=tot;swap(tmp[i][j],tmp[i-1][j]);del(tmp);while drop(tmp,tt) do del(tmp);o.push(dep+1,i,j,3);dfs(dep+1,tmp,tt);end;end;
end;var i,j,t:byte;
beginassign(input,'mayan.in');reset(input);assign(output,'mayan.out');rewrite(output);readln(limit); t:=0;for i:=1 to 5 do beginfor j:=1 to 7 do beginread(a[i][j]);if a[i][j]=0 then break else inc(t);end;readln;end;Dfs(0,a,t);writeln(-1);
end.
这篇关于搜索 MAYAN的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
