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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
BestSupport
0 / 0 / 0
Регистрация: 07.01.2013
Сообщений: 53
#1

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

04.03.2014, 03:19. Просмотров 1198. Ответов 2
Метки нет (Все метки)

Вот такая задачка:
В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).

Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол.

Входные данные

Во входном файле INPUT.TXT задано два числа N и M - размеры таблицы (1<=N<=20, 1<=M<=20). Затем идет N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (числа от 0 до 100).

Выходные данные

В выходной файл OUTPUT.TXT выведите минимальную сумму, потратив которую можно попасть в правый нижний угол.
А вот мое решение задачки, однако не проходит 1 тест, подскажите что я не учел?
C++ (Qt)
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
#include <iostream>
#include <stdio.h>
#include <iso646.h>
#include <math.h>
using namespace std;
int m,n,i,j,k;
int a[101][101],b[101][101];
int main()
{ freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  cin >> n >> m;
    for (i = 1; i <= n; i++) 
    {
        for (j = 1; j <= m; j++)
        {       
            cin >> a[i][j];
            b[0][j]=100001;
            b[j][0]=100001;
        }
    }
    b[0][1]=0;
    b[1][0]=0;
    for (i = 1; i <= n; i++) 
    {
        for (j = 1; j <= m; j++)
        {
            b[i][j]=min(b[i-1][j],b[i][j-1])+a[i][j];
        }
    
    }
cout << b[n][m];
return 0; }
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.03.2014, 03:19
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол (C++):

Определить минимальную сумму которую придётся заплатить за трафик - C++
Здравствуйте! Объясните мне, пожалуйста, как надо решить данную задачу? Вот тз: В Москве начал работать новый оператор сотовой связи,...

Найти минимальную сумму, заплатив которую игрок может попасть в правый нижний угол - Fortran
Задача 1413-1413 Ограничение по времени на тест 1 seconds, ограничение по памяти на тест 64 megabytes В прямоугольной таблице N...

Помочь черепашке попасть в правый нижний угол - Turbo Pascal
помогите доделать пожалуйста, выдает ошибку. На квадратной доске расставлены целые неотрицательные числа. Черепашка, находящаяся в...

Поставить элемент в правый нижний угол - HTML, CSS
есть &lt;div&gt; &lt;Table&gt;&lt;/table&gt; &lt;a href=&quot;#&quot;/&gt; &lt;/div&gt; как ссылку поместить в правый нижний угол...

Шахматы: Переместить короля в правый нижний угол - PascalABC.NET
Дана прямоугольная доска размером n×m (n строк и m столбцов). В левом верхнем углу этой доски находится шахматный король, которого...

Массовое добавление логотипа в правый нижний угол - Photoshop
Имеются фотографии разного размера. Чтобы добавить логотип ко всем фотографиям, сначала я создаю action. Поскольку мне надо добавить...

2
reckless91
30 / 30 / 1
Регистрация: 01.11.2013
Сообщений: 63
04.03.2014, 08:52 #2
Могу предложить идею, но реализация ляжет на Ваши плечи
Допустим, возьмем матрицу 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 минут
У тебя все работает правильно!!!
1
BestSupport
0 / 0 / 0
Регистрация: 07.01.2013
Сообщений: 53
04.03.2014, 12:17  [ТС] #3
я смотрю не по мин. двух соседей, а минимум суммы пути в i,j клетке

Добавлено через 8 минут
А все, нашел, здесь
C++
1
2
 b[0][j]=100001;
            b[j][0]=100001;
присваивал не правильно границы
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.03.2014, 12:17
Привет! Вот еще темы с ответами:

Сдвинуть вложенный див в правый нижний угол - HTML, CSS
Так возникла другая проблема. Нужно сделать портфолио Делаю так создаю div, вставляю в него фоновое изображение (background) ...

Переместить минимальный элемент матрицы в правый нижний угол - Pascal ABC
Путем перестановки строк и столбцов переместить минимальный элемент массива F(M, M) в правый нижний угол. Const M=10; a=-2.7;...

Уменьшение формы и сдвиг ее в правый нижний угол, над панелью задач - Delphi
Здарова, народ! Я написал простенький плеер, но мне нужно сделать кнопку (или пункт в главном меню) чтобы при нажатии на нее плеер...

Рисование прямоугольника получается только если вести курсор в правый нижний угол - C#
Пытаюсь сделать программу, которая рисует прямоугольники. Но столкнулся с проблемой: прямоугольник рисуется только вперед и вниз, т.е. если...


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

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

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