【题目解析】蓝桥杯23国赛C++中高级组 - 斗鱼养殖场

【题目解析】蓝桥杯23国赛C++中高级组 - 斗鱼养殖场

题目链接跳转：点击跳转

前置知识：

1. 了解过基本的动态规划。
2. 熟练掌握二进制的位运算。

题解思路

这是一道典型的状压动态规划问题。设 $d{p}_{i,j}$ 表示遍历到第 $i$ 行的时候，当前行以 $j_{(base2)}$ 的形式排列乌龟可以构成的方案数。

对于每一行的方案，我们可以用一个二进制来表示。例如二进制数字 $10100$，表示有一个横向长度为 $5$ 的场地中，第 $1,3$ 号位置分别放置了一只小乌龟。因此，每一种摆放状态都可以用一个二进制数字来表示。我们也可以通过遍历的方式来遍历出二进制的每一种摆放状态。

首先，我们预处理出横排所有放置乌龟的合法情况。根据题意，两个乌龟不能相邻放置，因此在二进制中，不能有两个 $1$ 相邻。如何预处理出这种情况呢？我们可以使用位运算的方法：

如果存在一个二进制数字有两个 $1$ 相邻，那么如果我们对这个数字 $x$ 进行位运算操作 (x << 1) & x 的结果或 (x >> 1) & x 的结果必定大于等于 $1$。我们通过把这种情况排除在外。同时，我们还需要注意有些格子中不能放置乌龟。这一步也可以通过二进制的方法预处理掉，如果网箱在第 $i$ 一个格子中不能放置乌龟，那么在枚举所有方案数的时候直接忽略掉第 $i$ 位为 $1$ 的情况即可。

接下来如何保证上下两行的乌龟不冲突？假如上一行的摆放状态是 $y$，当前行的摆放状态为 $j$，如果 i & j 的结果大于等于 $1$，也可以证明有两个数字 $1$ 在同一位置上。因此我们也需要把这种情况排除在外。

综上所述，我们可以得出状态转移方程：$d{p}_{i,j}=d{p}_{i,j}+d{p}_{i-1,k}$。其中，$j$ 和 $k$ 表示所有横排合法的方案。答案就是 $\mathtt{ANS}={\sum }_{j=0}^{2^M-1}d{p}_{N,j}$。

状态的初始化也很简单，另 $d{p}_{0,0}=1$​，表示一只乌龟都不放有一种摆放方案。

时间复杂度

通过观察上述代码，在枚举所有状态和转移状态的时候有三层循环，分别是枚举当前行、枚举当前行的合法摆放情况以及枚举上一行的摆放情况。因此总时间复杂度约为 $O(n\times 2^M\times 2^M)=O(n\times 2^{M^2})=O(n\times 4^M)$。但由于合法的摆放数量远远少于 $2^M$，因此实际情况下程序运行的速度会快许多。

代码实现

本题的代码实现如下。在输出的时候需要减一，因为不放置也是一种合法情况，根据题目要求需要把这一合法情况排除。

#include <iostream>
using namespace std;const int MOD = 1e9+7;
int n, m, ans;
int arr[505][505];
// 所有横排合法的情况。
int terrain[505];
int ok[1050], cnt;
int dp[505][1050];int main(){cin >> n >> m;for (int i=1; i<=n; i++){for (int j=1; j<=m; j++){cin >> arr[i][j];}}// 预处理非法地形。for (int i=1; i<=n; i++){for (int j=1; j<=m; j++){terrain[i] = (terrain[i] << 1) + !arr[i][j];}}// 预处理出所有横排的合法情况。for (int i=0; i<(1<<m); i++){if (((i<<1)|(i>>1)) & i) continue;ok[++cnt] = i;}dp[0][1] = 1;// 枚举。for (int i=1; i<=n; i++){for (int s1=1; s1<=cnt; s1++){  // 枚举当前行。if (ok[s1] & terrain[i]) continue;for (int s2=1; s2<=cnt; s2++){  // 枚举上一行。if (ok[s2] & terrain[i-1]) continue;if (ok[s1] & ok[s2]) continue;dp[i][s1] = (dp[i][s1] + dp[i-1][s2]) % MOD;}}}// 统计答案。int ans = 0;for (int i=1; i<=cnt; i++)ans = (ans + dp[n][i]) % MOD;cout << ans - 1 << endl;return 0;
}

本题的 Python 代码如下，Python 可以通过本题的所有测试点：

MOD = int(1e9 + 7)
n, m, ans = 0, 0, 0
arr = [[0] * 505 for _ in range(505)]
terrain = [0] * 505
ok = [0] * 1050
dp = [[0] * 1050 for _ in range(505)]
cnt = 0def main():global n, m, cnt, ans# 输入 n 和 mn, m = map(int, input().split())# 输入 arr 数组for i in range(1, n + 1):arr[i][1:m + 1] = map(int, input().split())# 预处理非法地形for i in range(1, n + 1):for j in range(1, m + 1):terrain[i] = (terrain[i] << 1) + (1 - arr[i][j])# 预处理出所有横排的合法情况for i in range(1 << m):if ((i << 1) | (i >> 1)) & i:continuecnt += 1ok[cnt] = idp[0][1] = 1# 枚举for i in range(1, n + 1):for s1 in range(1, cnt + 1):  # 枚举当前行if ok[s1] & terrain[i]:continuefor s2 in range(1, cnt + 1):  # 枚举上一行if ok[s2] & terrain[i - 1]:continueif ok[s1] & ok[s2]:continuedp[i][s1] = (dp[i][s1] + dp[i - 1][s2]) % MOD# 统计答案ans = 0for i in range(1, cnt + 1):ans = (ans + dp[n][i]) % MODprint(ans - 1)if __name__ == "__main__":main()

再提供一个暴力解法用于对拍：

#include <iostream>
using namespace std;const int MOD = 1e9+7;
int n, m, ans;
int arr[505][505];
int dx[] = {0, 1, -1, 0};
int dy[] = {1, 0, 0, -1};// 深度优先搜索 Brute Force
void dfs(int x, int y){if (x > n) {ans += 1;ans %= MOD;return ;}if (y > m){dfs(x+1, 1);return ;}if (arr[x][y] == 0){dfs(x, y+1);return ;}// 不放鱼dfs(x, y+1);// 放鱼for (int i=0; i<4; i++){int cx = x + dx[i];int cy = y + dy[i];if (cx < 1 || cy < 1 || cx > n || cy > m) continue;if (arr[cx][cy] == 2) return ;}arr[x][y] = 2;dfs(x, y+1);arr[x][y] = 1;return ;
}int main(){cin >> n >> m;for (int i=1; i<=n; i++){for (int j=1; j<=m; j++){cin >> arr[i][j];}}// dfs 暴力dfs(1, 1);cout << ans-1 << endl;return 0;
}