【HDU 5965】扫雷【线性递推】

xiaoxiao2021-03-01  29

题意:

      给一个3*N的矩阵,第一行和第三行可能会有地雷,第二行没有地雷,第二行每个格子上都有1个数,表示在以该格子为中心的九宫格中一共有几个地雷。

      给出第二行每个格子上的数字,问安放地雷的方案。

 

思路:

      乍一看不会。

      然后再仔细想想,可以发现第一列的地雷数量决定了第二列的地雷数量,而第一列和第二列的数量决定了第三列的数量,由此可以进行如下递推。

      由此总共三种情况,对第一列进行枚举,dp【i】表示第 i 列有几个地雷,详细内容见代码。

      还有一点就是,在递推的时候可能会推出不符合实际的情况,出现这种情况的话,就需要令tmp = 0,因此每次递推结束之后都需要检验一遍。

代码:

#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #define rep(i,a,b) for(int i = a;i <= b;i++) using namespace std; const int N = 1e4+100; const int mod = 1e8+7; char s[N]; int dp[N],num[N]; int x[10] = {1,2,1}; int main() { int T; scanf("%d",&T); while(T--) { scanf("%s",s); int len = strlen(s); rep(i,1,len) { num[i] = s[i-1]-'0'; } int ans = 0; rep(i,0,2) { if(i > num[1]) break; int tmp = 1; dp[1] = i; tmp = tmp*x[i]%mod; rep(j,2,len) { if(j == 2){ dp[j] = num[1]-dp[1]; if(dp[j] < 0 || dp[j] > 2) {tmp = 0; break;} tmp = tmp*x[dp[j]]%mod; } else{ dp[j] = num[j-1]-dp[j-2]-dp[j-1]; if(dp[j] < 0 || dp[j] > 2) {tmp = 0; break;} tmp = tmp*x[dp[j]]%mod; } } dp[0] = 0, dp[len+1] = 0; //检验程序:检验此种情况是否合法 rep(i,1,len) { if(num[i] != (dp[i]+dp[i-1]+dp[i+1])) {tmp = 0; break;} } ans = (ans+tmp)%mod; } printf("%d\n",ans); } return 0; }

转载请注明原文地址: https://www.6miu.com/read-3100027.html

最新回复(0)