题解 P1312 【Mayan游戏】
Skywalker_David · · 题解
相当bt的一个搜索。 经过我的连夜奋战，终于这道题做出来了!!!!
由于工程量的浩大，所以有很多地方都出了错（惭愧啊！NOIP-2011-day1-T3-Mayan游戏【搜索】）
但是在这个过程中收获了很多....这才是最重要的额NOIP-2011-day1-T3-Mayan游戏【搜索】
先感慨一下把，
首先是敲代码用了接近两节课......慢...
接着调试，开始直接全是-1....NOIP-2011-day1-T3-Mayan游戏【搜索】....发现在再次消去时忘了数组的初始化..
然后改了，依然如此...郁闷 忘了回溯...（这是大错啊，搜索不回溯结果怎会对！！）接着改...不要看我这里说的很轻松，找这些错误超级难找，我几乎想放弃..坚持就是胜利！！
然后 依然-1.....蛋碎一地
接着发现消去的时候不对，整个没消干净...改了两次才对....
然后样例过了...提交对了7个点，令3个字典序不对，才发现我最后点到了x，y数组，就成了y为第一关键字了....这个好改...终于AC了！！！！
收获:
对于搜索，主要是状态的拓展，从一个状态拓展出n个状态，这n个状态每个有拓展出n个......无穷无尽（是不可能的),碰到结果就完成了。
当这个阶段的这个状态不正确时，就要回到上个阶段的某个状态，这时也就是回溯，回溯时千万不要忘了初始化当前状态，否则.....不堪设想。
对于要求字典序输出，则在搜索的时候按照最优先的作为首先搜索的对象即可，也就是首先拓展最优状态....
还有对于向这样的大规模搜索题，一定要首先算好所有情况以及要用的过程，保证到最正确，因为在写完后如果出错很难改。
这道题当左边有数的时候，可以不向左移，因为处于左边的那个格子向右移与这个格子向左移是一样的，而且右移优于左移..
所以按照关键字的优先顺序拓展状态，当遇到结果输出就ok了。
#01: Accepted (0ms, 580KB)
#02: Accepted (0ms, 580KB)
#03: Accepted (0ms, 580KB)
#04: Accepted (0ms, 580KB)
#05: Accepted (6ms, 580KB)
#06: Accepted (178ms, 580KB)
#07: Accepted (537ms, 580KB)
#08: Accepted (68ms, 580KB)
#09: Accepted (84ms, 580KB)
#10: Accepted (1318ms, 580KB)Accepted / 100 / 2193ms / 580KB
type
date=array[0..14,1..8] of longint; //这里还用了这样定义的数组，很好用
var
n,m,i,j,step:longint;
map,kao:array[0..14,1..8] of longint;
x,y,z:array[1..10] of longint;
procedure print;
var
i:longint;
begin
writeln(y[1]-1,' ',x[1]-1,' ',z[1]);
i:=2;
while z[i]<>0 do begin
writeln(y[i]-1,' ',x[i]-1,' ',z[i]);
inc(i);
end;
end;
procedure init;
begin
read(n);
for i:=1 to 5 do begin
read(m);
j:=1;
while m<>0 do begin
map[j,i]:=m;
inc(j);
read(m);
end;
end;
end;
function check(map:date):boolean;
var
i,j,k,ll:longint; f:boolean;
fmap:array[1..7,1..5] of boolean;
begin
f:=true;
while f do begin
f:=false;
fillchar(fmap,sizeof(fmap),false);
for i:=1 to 7 do
for j:=1 to 3 do
if (map[i,j]=map[i,j+1])and(map[i,j+1]=map[i,j+2])and(map[i,j]<>0) then begin
fmap[i,j]:=true;
fmap[i,j+1]:=true;
fmap[i,j+2]:=true;
f:=true;
end;
for j:=1 to 5 do
for i:=1 to 5 do
if(map[i,j]=map[i+1,j])and(map[i+1,j]=map[i+2,j])and(map[i,j]<>0)then begin
fmap[i,j]:=true;
fmap[i+1,j]:=true;
fmap[i+2,j]:=true;
f:=true;
end;
if f then begin
for i:=1 to 7 do
for j:=1 to 5 do
if fmap[i,j]=true then map[i,j]:=0;
for j:= 1 to 5 do begin
i:=0;
while i<=7 do begin
inc(i);
ll:=0;
if (map[i,j]>0)and(i>1) then begin
for k:= i downto 1 do
if map[k,j]=0 then inc(ll);
if ll>0 then
for k:=i to 14 do
map[k-ll,j]:=map[k,j];
end;
i:=i-ll;
end;
end;
end;
end;
kao:=map;
f:=true;
for i:=1 to 7 do
for j:=1 to 5 do
if map[i,j]>0 then begin
f:=false;
exit(false);
end;
if f then exit(true)
else exit(false);
end;
procedure dfs(step:longint;map:date);
var
i,j,k,s,t,ii:longint;
caa:date;
begin
caa:=map;
s:=step;
if step<n then //在规定步数内则移动各个格子
for j:=1 to 5 do
for i:=1 to 7 do
if map[i,j]>0 then //此处有格子
begin
if j+1<=5 then //右移
begin
if(map[i,j+1]>0)and(map[i,j+1]<>map[i,j])then//如果右面<>0
begin
t:=map[i,j];
map[i,j]:=map[i,j+1];
map[i,j+1]:=t;
s:=step+1;
x[s]:=i;
y[s]:=j;
z[s]:=1;
if ( check(map)) and (s=n) then begin
print;
halt;
end;
map:=kao;
if s=n then map:=caa
else begin
dfs(s,map);
map:=caa;
end;
end;
if map[i,j+1]=0 then //如果右面=0那么下落
begin
ii:=i;
while (map[ii,j+1]=0)and(ii>0) do
dec(ii);
inc(ii);
map[ii,j+1]:=map[i,j];
for k:=i to 7 do //j列下落
map[k,j]:=map[k+1,j];
s:=step+1;
x[s]:=i;
y[s]:=j;
z[s]:=1;
if ( check(map)) and (s=n) then begin
print;
halt;
end;
map:=kao;
if s=n then map:=caa
else begin
dfs(s,map);
map:=caa;
end;
end;
end;
if j-1>0 then //左移
begin
if map[i,j-1]=0 then //如果左面=0那么下落
begin
ii:=i;
while (map[ii,j-1]=0)and(ii>0) do
dec(ii);
inc(ii);
map[ii,j-1]:=map[i,j];
for k:=i to 7 do // j列下落
map[k,j]:=map[k+1,j];
s:=step+1;
x[s]:=i;
y[s]:=j;
z[s]:=-1;
if ( check(map)) and (s=n) then
begin
print;
halt;
end;
map:=kao;
if s=n then map:=caa
else begin
dfs(s,map);
map:=caa;
end;
end;
end;
end;
end;
begin
init;
step:=0;
dfs(step,map);
write('-1');
end.