首页 > 代码库 > vijos p1193 扫雷
vijos p1193 扫雷
描述
相信大家都玩过扫雷的游戏。那是在一个n*n的矩阵里面有一些雷,要你根据一些信息找出雷来。万圣节到了,“余”任过流行起了一种简单的扫雷游戏,这个游戏规则和扫雷一样,如果某个格子没有雷,那么它里面的数字表示和他8连通的格子里面雷的数目。现在棋盘是n*2的,第一列里某些格子是雷,而第二列没有雷,如:
o 1
* 2
* 3
* 2
o 2
* 2
* 2 (‘*‘代表有雷,‘o‘代表无雷)
由于第一类的雷有可能有多种方案满足第二列的数的限制,你的任务即根据第二列的信息求第一列雷有多少中摆放方案。
格式
输入格式
第一行为N,第二行有N个数,依次为第二列的格子中的数。(1<=N<=10000)
输出格式
一个数,即第一列中雷的摆放方案数。
样例1
样例输入1[复制]
21 1
样例输出1[复制]
2
限制
1s
题解:
在前两到状压题的影响下,我采用了当前到第几行,该行是否放了雷以及上一行是否放了雷,在状态转移的时候发现没有一点DP的味道。。。不过还是过了。。。
其实当第一行是否放雷确定后,那么后面的就都确定了,所以答案不会超过2,枚举第一行的状态即可
代码:
1.
1 var f:array[0..10100,0..1,0..1] of longint; 2 n,i,j,k:longint; 3 a:array[0..10100] of longint; 4 procedure init; 5 begin 6 readln(n); 7 for i:=1 to n do read(a[i]); 8 end; 9 procedure main;10 begin11 f[1,1,1]:=0;12 f[1,0,1]:=0;13 f[1,0,0]:=1;14 f[1,1,0]:=1;15 for i:=2 to n+1 do16 if a[i-1]=1 then17 begin18 f[i,1,0]:=f[i-1,0,0];19 f[i,1,1]:=0;20 f[i,0,1]:=f[i-1,1,0];21 f[i,0,0]:=f[i-1,0,1];22 end23 else24 if a[i-1]=2 then25 begin26 f[i,1,0]:=f[i-1,0,1];27 f[i,1,1]:=f[i-1,1,0];28 f[i,0,1]:=f[i-1,1,1];29 f[i,0,0]:=0;30 end31 else32 if a[i-1]=3 then33 begin34 f[i,1,0]:=0;35 f[i,1,1]:=f[i-1,1,1];36 f[i,0,1]:=0;37 f[i,0,0]:=0;38 end39 else40 begin41 f[i,1,0]:=0;42 f[i,1,1]:=0;43 f[i,0,0]:=f[i-1,0,0];44 f[i,0,1]:=0;45 end;46 writeln(f[n+1,0,1]+f[n+1,0,0]);47 end;48 begin49 assign(input,‘input.txt‘);assign(output,‘output.txt‘);50 reset(input);rewrite(output);51 init;52 main;53 close(input);close(output);54 end.
2.
1 var a,b:array[0..12000] of longint; 2 ans,i,n:longint; 3 function check:boolean; 4 var i,t:longint; 5 begin 6 b[2]:=a[1]-b[1]; 7 for i:=2 to n do 8 begin 9 t:=b[i]+b[i-1];10 if (t>a[i]) or (t+1<a[i]) then exit(false);11 b[i+1]:=a[i]-t;12 end;13 exit(b[i+1]<>1);14 end;15 16 begin17 assign(input,‘input.txt‘);assign(output,‘output.txt‘);18 reset(input);rewrite(output);19 readln(n);20 for i:=1 to n do read(a[i]);21 ans:=0;22 for i:=0 to 1 do23 begin24 b[1]:=i;25 if check then inc(ans);26 end;27 writeln(ans);28 close(input);close(output);29 end.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。