Форум программистов, компьютерный форум CyberForum.ru

Найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Как узнать, сколько на дисках свободного места http://www.cyberforum.ru/cpp-beginners/thread1110566.html
Пожалуйста форумчане помогите с кодом как узнать сколько на дисках свободного места, надо чтоб в консоле под windows вывело на экран программа. приведите пожалуйста код.
C++ AT-команды 3G модему Доброго времени суток товарищи. Требуется по ТЗ считать смс с 3г модема. Гугл ничего дельного не подсказал, м.б. тут кто сталкивался? Интересуют наработки\советы\в какую сторону копать. Спасибо! http://www.cyberforum.ru/cpp-beginners/thread1110552.html
Операции над нечеткими множествами. Нужна литература C++
Здравствуйте, знающие люди можете немного помочь с литературой или примерами , кодами на С++ данной темы. Любой инфе буду рад, Спасибо.
Создать калькулятор, который (умножает, делит суммирует, отнимает и находит остаток) оперирует двумя числами C++
Доброго времени суток.Учусь программировать по книге Бьерна с++.Нужно создать калькулятор ,который (умножает,делит суммирует,отнимает и находит остаток) оперирует двумя числами. Притом он должен принимать на вход цифры записанные в числовой и строковой формах.вот что получилось у меня, но когда доходит до второго ввода программа закрывается и невозможно осуществить ввод.(по окончанию первого...
C++ Вывод данных на экран http://www.cyberforum.ru/cpp-beginners/thread1110524.html
#include "stdafx.h" #include <iostream> #include <cstdlib> #include <cstring> using namespace std; struct node { char *snm;
C++ Нужен ли C++ ? Привет скажите а нужен ли язык С++ ? Если без опыта работы не берут ? подробнее

Показать сообщение отдельно
reckless91
30 / 30 / 1
Регистрация: 01.11.2013
Сообщений: 63
04.03.2014, 08:52     Найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол
Могу предложить идею, но реализация ляжет на Ваши плечи
Допустим, возьмем матрицу 3х4

1 10 14 5
15 17 6 9
8 9 6 8

решение по выбору минимального среди 2-ух соседей неправильное... например, по такой логике получиться: 1 -> 10 -> 14 -> 5 -> 9 -> 8, а верным будет 1 -> 10 -> 14 -> 6 -> 6 -> 8

Следовательно надо смотреть дальше 2-ух соседей.

Добавлено через 29 минут
Алгоритм довольно прост в понимании (переработка Дейкстры впринципе)...

Самое главное заключается в том, что как бы вы не пытались - длина любого пути всегда константное число (для данной задачи), а вот веса у путей разные.
Исходя из этого можно провести диагональ на первом шаге через 1-ый элемент (а можно начать сразу со второго шага ) и занести в дополнительный массив b[N][M] в элемент b[0][0] = a[0][0] = 1.

Второй шаг - диагональ сдвигается вправо. Считаем веса для элементов "зачеркнутых" диагональю
b[0][1] = a[0][1] + b[0][0] = 11;
b[1][0] = a[1][0] + b[0][0] = 16;

Третий шаг - диагональ катит дальше.
b[0][2] = a[0][2] + b[0][1] = 25;
b[1][1] = "тонкое место" min(b[0][1], b[1][0]) + a[1][1] = 28
b[2][0] = a[2][0] + b[1][0] = 24;

4-ый
b[0][3] = a[0][3] + b[0][2] = 30;
b[1][2] = min(b[0][2], b[1][1]) + a[1][2] = 28;
b[2][1] = min(b[2][0], b[1][1]) + a[2][1] = 33;

5-ый
b[1][3] = min(b[0][3], b[1][2]) + a[1][3] = 37;
b[2][2] = min(b[1][2], b[2][1]) + a[2][2] = 34;

6-ой
b[2][3] = min(b[1][3], b[2][2]) + a[2][3] = 42 - Ваш ответ
Количество шагов равно (N + M - 1) если с первым шагом - без него же (N + M - 2) соответственно

Добавлено через 28 минут
У тебя все работает правильно!!!
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru