Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- /*мінімальне значення для позначення якщо неможливо здійснити рух вгору, вправо або по діагоналі*/
- #define C -9999
- /*
- 4 -3 4 2 -2 -3 3 3
- -1 1 -2 -1 6 2 -3 1
- 2 -1 5 3 -1 2 -1 3
- 1 -2 5 3 3 -4 -4 7
- -2 4 -2 3 -5 1 -3 -4
- -3 -2 -1 -5 3 1 -3 -2
- -2 -3 -2 3 -2 3 -1 -5
- 2 -1 -2 -3 -2 -1 4 3
- */
- using namespace std;
- int main() {
- /*n - розмір масиву*/
- /*u, r, d - значення для визначення максимального*/
- int n, u, r, d;
- cout << "Enter n: ";
- cin >> n;
- cout << endl;
- int **map = new int *[n], **maxMap = new int *[n];
- for (int i = 0; i < n; i++) {
- map[i] = new int[n];
- maxMap[i] = new int[n];
- }
- /*map - масив значень*/
- /*maxMap - масив максимальних значень*/
- for (int i = 0; i < n; i++)
- for (int j = 0; j < n; j++)
- cin >> map[i][j];
- /*ініціалізуємо кінцеву точку*/
- maxMap[0][n - 1] = map[0][n - 1];
- /*обраховуємо максимальні значення*/
- /*йдемо з кінцевої клітинки до початкової*/
- for (int i = 0; i < n; i++) {
- for (int j = n - 1; j >= 0; j--) {
- if (not (i == 0 && j == n - 1)) {
- u = r = d = C;
- /*якщо можливий рух вгору*/
- if (i - 1 >= 0) {
- u = maxMap[i - 1][j];
- }
- /*якщо можливий рух вправо*/
- if (j + 1 < n) {
- r = maxMap[i][j + 1];
- }
- /*якщо можливий рух по діагоналі*/
- if (j + 1 < n && i - 1 >= 0) {
- d = maxMap[i - 1][j + 1];
- }
- /*записуємо максимальне значення*/
- maxMap[i][j] = map[i][j] + max(u, max(r, d));
- }
- }
- }
- /*йдемо з першої клітинки до кінцевої*/
- int i = n - 1, j = 0;
- cout << endl << "Way: ";
- /*доки теперішня клітина != кінцевій*/
- while (not (i == 0 && j == n - 1)) {
- u = r = d = C;
- /*якщо можливий рух вгору*/
- if (i - 1 >= 0) {
- u = maxMap[i - 1][j];
- }
- /*якщо можливий рух вправо*/
- if (j + 1 < n) {
- r = maxMap[i][j + 1];
- }
- /*якщо можливий рух по діагоналі*/
- if (j + 1 < n && i - 1 >= 0) {
- d = maxMap[i - 1][j + 1];
- }
- /*рухаємось вгору якщо це max*/
- if (u == max(u, max(r, d))) {
- cout << "U";
- i--;
- }
- /*рухаємось вправо якщо це max*/
- if (r == max(u, max(r, d))) {
- cout << "R";
- j++;
- }
- /*рухаємось по діагоналі якщо це max*/
- if (d == max(u, max(r, d))) {
- cout << "D";
- i--; j++;
- }
- }
- cout << endl << "Max score: " << maxMap[n - 1][0] << endl;
- cout << endl << "Map of max values:" << endl;
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++)
- cout << maxMap[i][j] << " ";
- cout << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement