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

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

Восстановить пароль Регистрация
 
BestSupport
0 / 0 / 0
Регистрация: 07.01.2013
Сообщений: 47
04.03.2014, 03:19     Найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол #1
Вот такая задачка:
В прямоугольной таблице 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; }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.03.2014, 03:19     Найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол
Посмотрите здесь:

C++ Найти минимальную сумму положительных элементов диагоналей, параллельных побочной диагонали
Найти минимальную сумму диагонали матрицы, параллельной побочной C++
C++ Найти минимальную сумму
Путем перестановок строк и столбцов (целиком) элемент надо переместить в правый верхний угол подмассива (Перевести программу в c++) C++
C++ Расспаралеллеливание - найти минимальную сумму элементов по строкам
C++ Путем перестановок строк и столбцов элемент переместить в правый верхний угол подмассива (С Turbo Pascal на C++)
Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) C++
C++ Найти сумму и количество цифр числа, а также максимальную и минимальную его цифры
C++ Найти минимальную сумму в матрице по условию. Написать комментарий
Упорядочить строки матрицы, найти минимальную сумму строк C++
C++ Найти x и y и минимальную сумму x и y
Определить минимальную сумму которую придётся заплатить за трафик C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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 минут
У тебя все работает правильно!!!
BestSupport
0 / 0 / 0
Регистрация: 07.01.2013
Сообщений: 47
04.03.2014, 12:17  [ТС]     Найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол #3
я смотрю не по мин. двух соседей, а минимум суммы пути в i,j клетке

Добавлено через 8 минут
А все, нашел, здесь
C++
1
2
 b[0][j]=100001;
            b[j][0]=100001;
присваивал не правильно границы
Yandex
Объявления
04.03.2014, 12:17     Найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол
Ответ Создать тему
Опции темы

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