Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
0 / 0 / 0
Регистрация: 20.11.2016
Сообщений: 1
1

Найдите минимальную стоимость пути

20.11.2016, 23:18. Показов 426. Ответов 1
Метки нет (Все метки)

На клетчатом поле размером m×n в левом нижнем углу лежит игральная кость. За один ход её можно перекатить на клетку вправо или вверх. Стоимостью пути называется сумма чисел на верхней грани кубика во всех клетках пути (включая начальную и конечную).

Найдите минимальную стоимость пути в правый верхний угол.

Входные данные:
В первой строке два натуральных числа m и n (1 ≤ m, n ≤ 1000) — ширина и высота доски. Во второй строке три числа от 1 до 6 — числа на верхней, левой и передней грани кубика соответственно. Cумма чисел на противоположных гранях кубика равна 7, все числа на гранях кубика различны.

Выходные данные:
Выведите минимальную возможную стоимость пути.

Не проходят 2 теста, но никак не могу найти ошибку в коде.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
 
using namespace std;
 
struct dice {
    int u, l, f;
    dice rollUp() {
        return {f, l, 7 - u};
    };
    dice rollRight() {
        return {l, 7 - u, f};
    }
};
 
int field[1000][1000];
dice posC[1000][1000];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >>m >>n;
    cin >>posC[0][0].u >>posC[0][0].l >>posC[0][0].f;
    field[0][0] = posC[0][0].u;
    for (int i = 1; i < m; i++) {
        field[0][i] = field[0][i - 1] + posC[0][i - 1].l; 
        posC[0][i] = posC[0][i - 1].rollRight();
    }
    for (int i = 1; i < n; i++) {
        field[i][0] = field[i - 1][0] + posC[i - 1][0].f; 
        posC[i][0] = posC[i - 1][0].rollUp();
    }
    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++) {
            if (field[i][j - 1] + posC[i][j - 1].l < field[i - 1][j] + posC[i - 1][j].f) {
                field[i][j] = field[i][j - 1] + posC[i][j - 1].l;
                posC[i][j] = posC[i][j - 1].rollRight();
            } else {
                field[i][j] = field[i - 1][j] + posC[i - 1][j].f;
                posC[i][j] = posC[i - 1][j].rollUp();
            }
        }
    cout <<field[n - 1][m - 1];
    return 0;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.11.2016, 23:18
Ответы с готовыми решениями:

Посчитать минимальную стоимость пути из города А в город Б
Есть массив городов .Из каждого города есть маршруты к другим городам .Выглядит этот массив так ...

Если студент является отличником, то найдите его средний балл, в противном случае найдите минимальную оценку
Нужна ваша помощь в решении задачи : Имеется массив из итоговых оценок студента. Если студент...

Найдите стоимость акций через 6 месяцев, если начальная стоимость k долларов
каждый месяц на 0,6%. Найдите стоимость акций через 6 месяцев, если начальная стоимость k долларов

Найти минимальную стоимость конечного продукта
Существует 5 видов оборудования работающих с разной производительностью и вырабатывающие один и тот...

__________________
1
90 / 87 / 11
Регистрация: 20.11.2008
Сообщений: 724
21.11.2016, 10:53 2
есть 2 пути из точки (1, 1) в точку (2, 2) и они равноценны
Ваш алгоритм выберет один из них не обращая внимания на то, что путь нужно будет продолжить
2
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.11.2016, 10:53

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Как высчитать минимальную общую стоимость?
Задание: Вывести сведения о поставке (все поля таблицы Purchases), а также названия кинг (поля...

Определить минимальную стоимость перевозки AA тонн груза
Задача Перевозка груза Имя входного файла: стандартный ввод Имя выходного файла: стандартный...

Надо купить n дискет, заплатив минимальную стоимость
1 дискета стоит 11р.50к. 1 коробка (12 дискет) дискет стоит 114р.50к. 1 ящик (12 коробок) дискет...

Найти минимальную длину пути
На поверхности планеты, являющейся шаром с радиусом R, заданы две точки со своими широтой и...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.