nbhkdz.com冰点文库

NOIP2011 mayan游戏


NOIP2011 mayan 游戏 问题描述
Mayan puzzle 是最近流行起来的一个游戏。游戏界面是一个 7 行 5 列的棋盘,上面堆放着一些方块,方 块不能悬空堆放,即方块必须放在最下面一行,或者放在其他方块之上。游戏通关是指在规定的步数内消除所有 的方块,消除方块的规则如下: 1、 每步移动可以且仅可以沿横向(即向左或向右)拖动某一方块一格:当拖动这一方块时

, 如果拖动后到达的 位置(以下称目标位置)也有方块, 那么这两个方块将交换位置(参见输入输出样例说明中的图 6 到图 7); 如果目 标位置上没有方块,那么被拖动的方块将从原来的竖列中抽出,并从目标位置上掉落(直到不悬空,参见下面图 1 和图 2);

2、任一时刻,如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块,则它们将立即被消除(参 见图 1 到图 3)。 注意: a) 如果同时有多组方块满足消除条件,几组方块会同时被消除(例如下面图 4,三个颜色为 1 的方块和三 个颜色为 2 的方块会同时被消除,最后剩下一个颜色为 2 的方块)。 b) 当出现行和列都满足消除条件且行列共享某个方块时,行和列上满足消除条件的所有方块会被同时消除 (例如下面图 5 所示的情形,5 个方块会同时被消除)。

3、方块消除之后,消除位置之上的方块将掉落,掉落后可能会引起新的方块消除。注意:掉落的过程中将不 会有方块的消除。 上面图 1 到图 3 给出了在棋盘上移动一块方块之后棋盘的变化。棋盘的左下角方块的坐标为(0, 0),将位 于(3, 3)的方块向左移动之后,游戏界面从图 1 变成图 2 所示的状态, 此时在一竖列上有连续三块颜色为 4 的方块,满足消除条件,消除连续 3 块颜色为 4 的方块后,上方的 颜色为 3 的方块掉落,形成图 3 所示的局面。

第 1 页

2011-11-14

NOIP2011 mayan 游戏 输入文件
输入文件共 6 行。 第一行为一个正整数 n,表示要求游戏通关的步数。 接下来的 5 行,描述 7 ? 5 的游戏界面。每行若干个整数,每两个整数之间用一个空格隔 开,每行以一个 0 结束,自下向上表示每竖列方块的颜色编号(颜色不多于 10 种,从 1 开始顺序编号, 相同数字表示相同颜色)。 输入数据保证初始棋盘中没有可以消除的方块。

输出文件
如果有解决方案,输出n 行,每行包含3 个整数x,y,g,表示一次移动,每两个整数之间用一个空格隔开, 其中(x,y)表示要移动的方块的坐标,g 表示移动的方向,1 表示向右移动,-1 表示向左移动。注意:多组解 时,按照x 为第一关健字,y 为第二关健字,1优先于-1,给出一组字典序最小的解。游戏界面左下角的坐标 为(0,0)。 如果没有解决方案,输出一行,包含一个整数-1。

输入输出样例
hotel.in 3 10 210 2340 310 24340 hotel.out 211 311 301

第 2 页

2011-11-14

NOIP2011 mayan 游戏 输入输出样例说明
按箭头方向的顺序分别为图 6 到图 11

样例输入的游戏局面如上面第一个图片所示,依次移动的三步是:(2,1)处的方格向右移动,(3,1)处的方 格向右移动,(3,0)处的方格向右移动,最后可以将棋盘上所有方块消除。

数据范围
对于 30%的数据,初始棋盘上的方块都在棋盘的最下面一行; 对于 100%的数据,0 <n ? 5。

第 3 页

2011-11-14

NOIP2011 mayan 游戏 算法分析:dfs
1.主函数:读入数据,并判断 dfs 中是否找到解,没找到输出-1。 2.dfs:对 7 ? 5 中每个非 0 的点按照 x 从小到大,y 从小到大,先右后左进行枚举,注意右边界点不能向右, 左边界点不能向左,枚举时调用 move 函数并记录相应操作;每次枚举前要把原来的矩阵 copy 一份,便于回 溯;当超过 n 时,判断是否为空,如果为空就输出记录的操作。 3.move:首先是交换两个变量的位置,调用时用一个记号记录是向左还是向右。然后调用 fall 函数、wipe 函数(消块) 。注意,如果 wipe 函数生效,则要对所有点重新调用 fall 函数和 wipe 函数,直到 wipe 函数中没 有消掉任何块。 4.fall:判断该点下方是否有 0,如果有 0 就向下移,反之则无。 5.wipe:按横和纵两种情况,判断是否是超过 3 个同样的颜色连接在一起,如果有就标记它们为 true。需 要注意,等所有点都判断完再消去,防止一个点被用两次的情况。 调试的时候,可以对每个函数分别进行测试,这样有助于加快效率。个人感觉,3s 的时限,应该能过大部 分数据吧。听旁边的大牛说用 A*(启发式搜索)……。

program 格致中学朱稼乐; type state=array[1..10,1..10] of longint; arr=array[1..10] of longint; var map:state;len:arr; p:array[1..10] of record x,y,z:longint;end; n,i,j,tmp,t,tt,pt : longint; procedure doit(x,y,g:longint;var map:state; var len:arr); var tmp,i,j,k,color,t:longint; flag:boolean; begin if g=-1 then begin tmp:=map[x,y];map[x,y]:=map[x-1,y];map[x-1,y]:=tmp;end else if g=1 then begin tmp:=map[x,y];map[x,y]:=map[x+1,y];map[x+1,y]:=tmp;end; if map[x,y]=0 then begin for j:=y downto 1 do if map[x+g,j]=0 then break; map[x+g,j]:=map[x+g,y]; map[x+g,y]:=0;len[x+g]:=j; end;

第 4 页

2011-11-14

NOIP2011 mayan 游戏
repeat flag:=false; for i:=1 to 5 do for j:=1 to 7 do begin if map[i,j]=0 then continue; color:=map[i,j]; if i<=3 then begin t:=1; for k:=1 to 2 do if map[i+k,j]=color then inc(t); if t=3 then begin for k:=0 to 2 do map[i+k,j]:=0;flag:=true;end; end; if j>=3 then begin t:=1; for k:=1 to 2 do if map[i,j-k]=color then inc(t); if t=3 then begin for k:=0 to 2 do map[i,j-k]:=0;flag:=true;end; end; end; if flag then begin for i:=1 to 5 do begin for j:=1 to 7 do if map[i,j]=0 then break; for k:=j+1 to 7 do if map[i,k]<>0 then break; if map[i,k]=0 then continue else begin move(map[i,k],map[i,j],4*(len[i]-k+1)); for j:=j+len[i]-k+1 to 7 do map[i,j]:=0; end; end; for i:=1 to 5 do begin for j:=1 to 7 do if map[i,j]=0 then break; len[i]:=j-1; end; end; until not flag; end;

第 5 页

2011-11-14

NOIP2011 mayan 游戏
procedure dfs(max,depth:integer;map:state;len:arr); var bak:state; bak2:arr;i,j,zz,way:longint; begin zz:=0; for i:=1 to 5 do inc(zz,len[i]); if zz=0 then begin for i:=1 to pt do writeln(p[i].x-1,' ',p[i].y-1,' ',p[i].z); close(input);close(output);halt; end; if depth>max then exit; way:=0; inc(tt); bak:=map; bak2:=len; if tt>40000000 then begin writeln('-1');close(input);close(output);halt;end; for i:=1 to 5 do for j:=1 to len[i] do begin if i<5 then begin doit(i,j,1,map,len);inc(pt); p[pt].x:=i; p[pt].y:=j; p[pt].z:=1; dfs(max,depth+1,map,len); dec(pt); map:=bak; len:=bak2; end; if i>1 then begin doit(i,j,-1,map,len);inc(pt); p[pt].x:=i;p[pt].y:=j;p[pt].z:=-1; dfs(max,depth+1,map,len); dec(pt); map:=bak; len:=bak2; end; end; end; begin assign(input,'mayan.in');reset(input); assign(output,'mayan.out');rewrite(output); readln(n); for i:=1 to 5 do begin t:=0; while not eoln do begin read(tmp); if tmp<>0 then begin inc(t);map[i,t]:=tmp;end; len[i]:=t; end; readln; end; dfs(n,1,map,len); writeln('-1'); close(input); close(output); end.

第 6 页

2011-11-14


noip2011 解题报告 mayan游戏

noip2011 解题报告 mayan游戏_IT/计算机_专业资料。noip2011 解题报告 pascal版mayan 游戏 【问题描述】 Mayan puzzle 是最近流行起来的一个游戏。游戏界面是一个 ...

NOIP2011 mayan游戏

NOIP2011 mayan游戏_学科竞赛_高中教育_教育专区。NOIP2011 mayan游戏NOIP2011 mayan 游戏 问题描述 Mayan puzzle 是最近流行起来的一个游戏。游戏界面是一个 7 行...

NOIP2011提高组解题报告day1

NOIP2011提高组解题报告day1_学科竞赛_高中教育_教育专区。NOIP2011提高组解题报告...mayan 游戏 【问题描述】 Mayan puzzle 是最近流行起来的一个游戏。游戏界面是...

NOIP 2011 提高组 day1 题解

NOIP 2011 提高组 day1 题解_其它考试_资格考试/认证_教育专区。NOIP2011 题...复杂度 O(NK) 期望得分 100 3.Mayan 游戏 思路 1:直接输出-1 复杂度 O(...

2011题解

第十七届全国青少年信息学奥林匹克联赛复赛试题 (NOIP2011 提高组) Day1 铺地毯...【考察知识点】 DFS 【思路】 第三题竟然是 iPhone 上 Mayan Puzzle 游戏的...

十七届信息学奥赛提高组复赛第一天(NOIP2011)

十七届信息学奥赛提高组复赛第一天(NOIP2011)十七届信息学奥赛提高组复赛第一天(...mayan 游戏 mayan mayan mayan.in mayan.out 3 秒 10 10 有 全文比较(过滤...

NOIP2011提高组 第一天 Day1试题

NOIP2011 提高组 Day2 4页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出...传统 传统 mayan 游戏 mayan mayan mayan.in mayan.out 3秒 10 10 有 二....

NOIP2011提高组复赛试题与简解(转载)

NOIP2011提高组复赛试题与简解(转载)_中考_初中教育_教育专区。NOIP2011提高组...【时间复杂度】 O(nk+nlogn) mayan 游戏 【问题描述】 Mayan puzzle 是最近...

2011noip复赛解题报告(未完)

2011noip复赛解题报告(未完)_五年级语文_语文_小学教育_教育专区。DAY1 1.铺...3.Mayan 游戏 (mayan.cpp/c/pas) 数据范围】 【数据范围】 30%的数据 初始...

2011noip复赛解题报告day1

2011noip解题报告 13页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出...3.Mayan 游戏 (mayan.cpp/c/pas) 【数据范围】 对于 30%的数据,初始棋盘上...