NOIP2011第一天第三题怎么做?

NOIP2011第一天第三题怎么做?
NOIP2011第一天第三题怎么做?

NOIP2011第一天第三题怎么做?
比较复杂的搜索题……
剪枝方案：
（1）\x05每次搜索只搜到最高层即可,不用全部搜索……
（2）\x05当左右两个点相同时,移动和不移动是一样的,则我们不用移动……
（3）\x05搜索每一个点,我们会发现将F[i,j]向右移和将F[i+1,j]向左移是一样的,则我们只搜索向右移的……
注意要把数组开大些,防止移动时出错（我一开始开到5*7的数组,总是有几个点过不去,郁闷了好长时间……）,转移状态时不要出错……
program mayan;
type tyy=array[0..10,0..10] of longint;
var f:tyy;
n,i,a,b:longint;
x,y,z:array[0..10] of longint;
function jiancha(ff:tyy):boolean; //检查最低层是否都消去
var i,j:longint;
begin
for i:=0 to 4 do
if ff[i,0]0 then exit(false);
exit(true)
end;
procedure print;
var i:longint;
begin
for i:=1 to n do
writeln(x[i],' ',y[i],' ',z[i]);
close(input); close(output);
halt; //若有多种方案则以x为第一关键字按字典序输出,因为搜索时按x从0到4搜索的,故找到第一种方案是可以直接退出程序
end;
procedure dfs(k:longint; ff:tyy);
forward;
procedure check(k:longint; ff:tyy);
var bt:array[0..4,0..7] of boolean;
boo:boolean;
i,j,kk,t:longint;
begin
boo:=false;
while (not boo) do //判断是否能下降,若没有下降则说明没有能消除的方块
begin
for i:=0 to 4 do for j:=0 to 7 do bt[i,j]:=false; //初始化bt,记录能否消除
for i:=0 to 4 do for j:=0 to 7 do //消除三个连续相同的
begin
if ff[i,j]=0 then continue;
if (ff[i,j]=ff[i,j+1])and(ff[i,j+1]=ff[i,j+2])and(ff[i,j]0)then
begin
bt[i,j]:=true;
bt[i,j+1]:=true;
bt[i,j+2]:=true;
end;
if (ff[i,j]=ff[i+1,j])and(ff[i+1,j]=ff[i+2,j])and(ff[i,j]0)then
begin
bt[i,j]:=true;
bt[i+1,j]:=true;
bt[i+2,j]:=true;
end;
end;
for i:=0 to 4 do for j:=0 to 7 do if bt[i,j] then ff[i,j]:=0;
boo:=true;
for i:=0 to 4 do //下降
for j:=0 to 7 do
if ff[i,j]=0 then
begin
t:=j;
while (t7 then break;
for kk:=0 to t-j do
begin
ff[i,j+kk]:=ff[i,t+kk];
ff[i,t+kk]:=0;
end;
boo:=false;
end;
if boo then break;
end;
if (kn+1)and(jiancha(ff)) then exit; //若不是在规定步数走完,则退出
if (k=n+1)and(jiancha(ff)) then print; //若恰好在规定步数消完,则输出
dfs(k,ff);
end;
procedure dfs(k:longint; ff:tyy);
var i,j,tt:longint;
begin
if k>n then exit;
for j:=0 to 4 do
for i:=0 to 7 do
begin
if (ff[j,i]=0)then break;
if (ff[j-1,i]=0)and(j0)and(ff[j,i]ff[j-1,i]) then //若可以交换,则尝试交换
begin
x[k]:=j; y[k]:=i; z[k]:=-1;
tt:=ff[j,i]; ff[j,i]:=ff[j-1,i]; ff[j-1,i]:=tt;
check(k+1,ff);
tt:=ff[j,i]; ff[j,i]:=ff[j-1,i]; ff[j-1,i]:=tt;
x[k]:=0; y[k]:=0; z[k]:=0;
end;
if j=4 then continue; //若搜索到最后一列,则不能向右移动,退出本次循环
if ff[j,i]=ff[j+1,i] then continue;
x[k]:=j; y[k]:=i; z[k]:=1;
tt:=ff[j,i]; ff[j,i]:=ff[j+1,i]; ff[j+1,i]:=tt;
check(k+1,ff);
tt:=ff[j,i]; ff[j,i]:=ff[j+1,i]; ff[j+1,i]:=tt;
x[k]:=0; y[k]:=0; z[k]:=0;
end;
end;
begin
assign(input,'mayan.in');reset(input);
assign(output,'mayan.out');rewrite(output);
readln(n);
for i:=0 to 4 do //读入数据
begin
b:=-1;
repeat
read(a);
inc(b);
f[i,b]:=a;
until a=0;
end;
x[0]:=-1; y[0]:=-1; z[0]:=-2; //将x、y、z数组初始化
dfs(1,f);
writeln('-1'); //若没有解决方案,输出-1
close(input); close(output);
end.
自我感觉程序比较慢,各位大神应该还有更好的方法,希望能交流一下,欢迎鄙视……