首页 > 代码库 > vijos p1193 扫雷

vijos p1193 扫雷

2024-07-15 17:59:23   219人阅读

 

描述

相信大家都玩过扫雷的游戏。那是在一个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.
View Code

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.
View Code

 


联系
我们