1. 方格取数问题: 在一个有m×n个方格的棋盘中,每个方格中有一个正整数。现要从方格中取数,使任意 2 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘,按照取数要求编程找出总和最大的数。 输入:第 1 行有 2 个正整数 m 和 n,分别表示棋盘的行数和列数。接下来的 m 行,每行有 n 个正整数,表示棋盘方格中的数。 输入样例: 3 3 1 2 3 3 2 3 2 3 1 输出:程序运行结束时,将取数的最大总和输出 输出样例:
时间: 2024-02-11 17:09:34 浏览: 43
这一个经典的图论问题,可以使用搜索或动态规划算法来解决。
动态规划算法的状态转移方程为:
dp[i][j][0]表示从第i行第j列取数,且该位置没有取数的最大值,dp[i][j][1]表示从第i行第j列取数,且该位置取数的最大值。
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1], dp[i][j-1][0], dp[i][j-1][1])
dp[i][j][1] = dp[i][j][0] + s[i][j]
其中,s[i][j]表示第i行第j列的数值。
最终的答案为max(dp[m][n][0], dp[m][n][1])。
代码实现如下:
```python
m, n = map(int, input().split())
s = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
s[i][1:n+1] = list(map(int, input().split()))
dp = [[[0] * 2 for _ in range(n+1)] for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1], dp[i][j-1][0], dp[i][j-1][1])
dp[i][j][1] = dp[i][j][0] + s[i][j]
print(max(dp[m][n][0], dp[m][n][1]))
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)