数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学从矩阵左上角到右下角获得最大点数并在C++中返回
在本教程中，我们将讨论一个程序，该程序用于查找从矩阵左上角到右下角的最大点数并返回。
为此，我们将得到一个由 #-阻塞路径、*-点数和 .-允许路径组成的矩阵。我们的任务是从一个角到另一个角（向右和向下移动）然后再返回（向左和向上移动），以收集最大点数。
示例
#include <bits/stdc++.h>
#define MAX 5
#define N 5
#define M 5
#define inf 100000
using namespace std;
//calculating points
int cost(char grid[][M], int row1, int col1, int row2, int col2) {
if (row1 == row2 && col1 == col2) {
if (grid[row1][col1] == '*')
return 1;
return 0;
}
int ans = 0;
if (grid[row1][col1] == '*')
ans++;
if (grid[row2][col2] == '*')
ans++;
return ans;
}
//calculating maximum points
int solve(int n, int m, char grid[][M], int dp[MAX][MAX][MAX], int row1, int col1, int row2) {
int col2 = (row1 + col1) - (row2);
if (row1 == n - 1 && col1 == m - 1 && row2 == n - 1 && col2 == m - 1)
return 0;
if (row1 >= n || col1 >= m || row2 >= n || col2 >= m)
return -1 * inf;
if (dp[row1][col1][row2] != -1)
return dp[row1][col1][row2];
int ch1 = -1 * inf, ch2 = -1 * inf;
int ch3 = -1 * inf, ch4 = -1 * inf;
if (grid[row1][col1 + 1] != '#' &&
grid[row2 + 1][col2] != '#')
ch1 = cost(grid, row1, col1 + 1, row2 + 1, col2) + solve(n, m, grid, dp, row1, col1 + 1, row2 + 1);
if (grid[row1][col1 + 1] != '#' &&
grid[row2][col2 + 1] != '#')
ch2 = cost(grid, row1, col1 + 1, row2, col2 + 1) + solve(n, m, grid, dp, row1, col1 + 1, row2);
if (grid[row1 + 1][col1] != '#' &&
grid[row2][col2 + 1] != '#')
ch3 = cost(grid, row1 + 1, col1, row2, col2 + 1) + solve(n, m, grid, dp, row1 + 1, col1, row2);
if (grid[row1 + 1][col1] != '#' &&
grid[row2 + 1][col2] != '#')
ch4 = cost(grid, row1 + 1, col1, row2 + 1, col2) + solve(n, m, grid, dp, row1 + 1, col1, row2 + 1);
return dp[row1][col1][row2] = max({ch1, ch2, ch3, ch4});
}
int wrapper(int n, int m, char grid[N][M]) {
int ans = 0;
int dp[MAX][MAX][MAX];
memset(dp, -1, sizeof dp);
if (grid[n - 1][m - 1] == '#' || grid[0][0] == '#')
ans = -1 * inf;
if (grid[0][0] == '*')
ans++;
grid[0][0] = '.';
if (grid[n - 1][m - 1] == '*')
ans++;
grid[n - 1][m - 1] = '.';
ans += solve(n, m, grid, dp, 0, 0, 0);
return max(ans, 0);
}
int main() {
int n = 5, m = 5;
char grid[N][M] = {
{ '.', '*', '.', '*', '.' },
{ '*', '#', '#', '#', '.' },
{ '*', '.', '*', '.', '*' },
{ '.', '#', '#', '#', '*' },
{ '.', '*', '.', '*', '.' }
};
cout << wrapper(n, m, grid) << endl;
return 0;
}输出
8
更新于： 2020年9月9日
287 次浏览
广告