HDu 5965掃雷(繰返し)
2469 ワード
雷を掃く
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
掃雷ゲームは朝とルルが特に好きな知能ゲームで、彼女たち二人は最近夢中になって抜け出せない.
このゲームのインタフェースは行列であり,行列の中にはいくつかの格子に地雷があり,残りの格子には地雷がない.ゲーム中、格子は自分の知っている状態と未知の状態にある可能性があります.既知の格子に地雷がない場合、その格子には、この格子8に連通する隣接する格子中の地雷の総数を示す桁数が書かれている.
現在、朝とルルは3行のN列(いずれも1から連続正整数番号)の行列の中でゲームを行い、この行列の中で2行目の格子はすべて自分で知っていて、その中に地雷はありません.他の2行は未知であり、その中の地雷の総数も未知である.
朝とルルは、1行目と3行目に地雷を合法的に埋める案がどれだけあるか知りたいと思っています.
Input
複数組のテストデータを含み、最初の行には正の整数Tがあり、データグループ数を表す.
各グループのデータは、1行が数字のみからなる長さNの非空文字列からなり、行列が3行N列であることを示し、文字列のi番目の数字文字は行列の2行目i番目の格子の数字を表す.
文字列長N<=10000、データセット数<=100を保証します.
Output
1行あたりわずか1桁の数字で、地雷の設置案数mod 1億7000万7千万件の結果を示した.
Sample Input
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
掃雷ゲームは朝とルルが特に好きな知能ゲームで、彼女たち二人は最近夢中になって抜け出せない.
このゲームのインタフェースは行列であり,行列の中にはいくつかの格子に地雷があり,残りの格子には地雷がない.ゲーム中、格子は自分の知っている状態と未知の状態にある可能性があります.既知の格子に地雷がない場合、その格子には、この格子8に連通する隣接する格子中の地雷の総数を示す桁数が書かれている.
現在、朝とルルは3行のN列(いずれも1から連続正整数番号)の行列の中でゲームを行い、この行列の中で2行目の格子はすべて自分で知っていて、その中に地雷はありません.他の2行は未知であり、その中の地雷の総数も未知である.
朝とルルは、1行目と3行目に地雷を合法的に埋める案がどれだけあるか知りたいと思っています.
Input
複数組のテストデータを含み、最初の行には正の整数Tがあり、データグループ数を表す.
各グループのデータは、1行が数字のみからなる長さNの非空文字列からなり、行列が3行N列であることを示し、文字列のi番目の数字文字は行列の2行目i番目の格子の数字を表す.
文字列長N<=10000、データセット数<=100を保証します.
Output
1行あたりわずか1桁の数字で、地雷の設置案数mod 1億7000万7千万件の結果を示した.
Sample Input
2 22 000
Sample Output
6 1 题意：扫雷小游戏，3*n的矩形，中间的一行全是数字，表示周围的雷数，求有多少种的雷的分布方案。 思路：递推。以num[i]记录第i列给的数字，dp[i]记录第i列的雷数，枚举第一列的雷数dp[0]，则有 dp[1]=num[0]-dp[0], dp[2]=num[1]-dp[1]-dp[0] .... 递推下去即可，最后，统计一下对答案的贡献度就好。 代码：#includeusing namespace std; typedef long long ll; const int maxn=11111; const int mod=1e8+7; char s[maxn]; int num[maxn],dp[maxn]; int main() { int T; scanf("%d",&T); while(T--) { scanf("%s",s); int n=strlen(s); memset(dp,0,sizeof(dp)); for(int i=0;i 2)break; int j; for(j=2;j<=n;j++) { int k=num[j-1]-dp[j-1]-dp[j-2]; if(k>2||k<0) break; dp[j]=k; } if(j<=n)continue; if(dp[n-1]+dp[n]!=num[n])continue; ll res=1; for(int i=1;i<=n;i++) { if(dp[i]==0||dp[i]==2) res*=1; else res*=2; res%=mod; } ans+=res; ans%=mod; } printf("%d
",ans); } return 0; }