UC知道请教一道pascal题,写思路
来源：百度知道 编辑：UC知道 时间：2024/06/07 17:18:01
描述 Description
相信大家都玩过扫雷的游戏。那是在一个n*n的矩阵里面有一些雷，要你根据一些信息找出雷来。万圣节到了，“余”任过流行起了一种简单的扫雷游戏，这个游戏规则和扫雷一样，如果某个格子没有雷，那么它里面的数字表示和他8连通的格子里面雷的数目。现在棋盘是n*2的，第一列里某些格子是雷，而第二列没有雷，如：
o 1
* 2
* 3
* 2
o 2
* 2
* 2 ('*'代表有雷，'o'代表无雷)
由于第一类的雷有可能有多种方案满足第二列的数的限制，你的任务即根据第二列的信息求第一列雷有多少中摆放方案。
输入格式 Input Format
第一行为N，第二行有N个数，依次为第二列的格子中的数。（1<=N<=10000）
输出格式 Output Format
一个数，即第一列中雷的摆放方案数。
样例输入 Sample Input
2
1 1
样例输出 Sample Output
2
我知道是用递推做,请写出递推式(5分),并指出每个变量指什么.最好贴程序(10分);谢谢各位大牛!!!!!!!!
明白了!谢谢409716042!!!!
相信大家都玩过扫雷的游戏。那是在一个n*n的矩阵里面有一些雷，要你根据一些信息找出雷来。万圣节到了，“余”任过流行起了一种简单的扫雷游戏，这个游戏规则和扫雷一样，如果某个格子没有雷，那么它里面的数字表示和他8连通的格子里面雷的数目。现在棋盘是n*2的，第一列里某些格子是雷，而第二列没有雷，如：
o 1
* 2
* 3
* 2
o 2
* 2
* 2 ('*'代表有雷，'o'代表无雷)
由于第一类的雷有可能有多种方案满足第二列的数的限制，你的任务即根据第二列的信息求第一列雷有多少中摆放方案。
输入格式 Input Format
第一行为N，第二行有N个数，依次为第二列的格子中的数。（1<=N<=10000）
输出格式 Output Format
一个数，即第一列中雷的摆放方案数。
样例输入 Sample Input
2
1 1
样例输出 Sample Output
2
我知道是用递推做,请写出递推式(5分),并指出每个变量指什么.最好贴程序(10分);谢谢各位大牛!!!!!!!!
明白了!谢谢409716042!!!!
简单的递推，直接给出代码：
var
n,i,ans:integer;
a,f:array[0..10001]of integer;
procedure work;
begin
for i:=3 to n do
begin
f[i]:=a[i-1]-f[i-1]-f[i-2];
if (f[i]<0)or(f[i]>1) then exit;
end;
if f[n-1]+f[n]<>a[n] then exit;
inc(ans);
end;
begin
readln(n);
for i:=1 to n do read(a[i]);
case a[1] of
3:ans:=0;
2:begin
f[1]:=1;f[2]:=1;work;
end;
1:begin
f[1]:=1;work;
fillchar(f,sizeof(f),0);f[2]:=1;work;
end;
0:work;
end;
writeln(ans);
end.
解方程组 求出自由变元数X 答案就是2^X.
DP题，dp[i][j]=dp[i-1][(2*j)%8]+dp[i-1][(2*j+1)%8]；