Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.54/13: Рейтинг темы: голосов - 13, средняя оценка - 4.54
5 / 5 / 2
Регистрация: 21.03.2011
Сообщений: 79
1

Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку.

03.11.2011, 21:37. Показов 2676. Ответов 16
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
кому не трудно помогите сделать. если не трудно вам написать код.

Дана прямоугольная таблица nxn клеток. В каждой клетке содержится либо цифра (от 0 до 9), либо символ "x" (препятствие). Стоимостью пути называется сумма цифр на посещенных клетках. Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на соседнюю правую или нижнюю клетку.

Входные данные
В первой строке записаны два числа n и m (1<=n<=80, 1<=m<=80, n + m > 2) - количества строк и столбцов таблицы соответственно. Далее в n строках записано по m символов, описывающих таблицу. Гарантируется, что клетки (1, 1) и (n, m) не содержат "x".

Выходные данные
Выведите искомую стоимость или фразу "see you later", если искомого пути не существует.

Пример

Ввод
3 5
0044x
300x7
00100

Вывод
5
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.11.2011, 21:37
Ответы с готовыми решениями:

Минимальный путь из левой верхней в правую нижнюю клетку таблицы.
Не могу понять в чем ошибка...помогите. Химическая тревога (Время: 1 сек. Память: 16 Мб...

Сколько есть способов попасть в правую нижнюю клетку
В прямоугольной таблице N×M вначале игрок находится в левой верхней клетке. За один ход ему...

Сколько есть способов у игрока попасть в правую нижнюю клетку
В прямоугольной таблице N×M вначале игрок находится в левой верхней клетке. За один ход ему...

В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N
В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из...

16
Заблокирован
03.11.2011, 21:48 2
Montanaa, толи я задачу не понял, толи у меня получилось, что цена пути из примера - 1, а не 5
0
1552 / 918 / 193
Регистрация: 26.03.2010
Сообщений: 3,105
03.11.2011, 21:49 3
Все там верно, 5.
0, 0 -> 0, 1 -> 0, 2 -> 1, 2 -> 2, 2 -> 2, 3 -> 2, 4
0
Заблокирован
03.11.2011, 21:51 4
neske, аааа... туплю)
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
03.11.2011, 21:52 5
динамика..
0
5 / 5 / 2
Регистрация: 21.03.2011
Сообщений: 79
03.11.2011, 21:56  [ТС] 6
да, динамика)
0
6 / 6 / 3
Регистрация: 30.08.2011
Сообщений: 32
03.11.2011, 21:57 7
У обоих правильный ответ, так как двигаться можно по-разному. Движение вниз не является главным. Тема, ИМХО не для начинающих. Тут еще и бэккинг придется задействовать, если, скажем, на последней строчке, двигаясь вправо, упремся в "х".
0
Higher
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
03.11.2011, 22:00 8
Цитата Сообщение от valeriikozlov Посмотреть сообщение
динамика..
Угу.
Алгоритм примерно такой:
Завести матрицу n * m и заполнять ее.
Пусть d - матрица под динамику, a - исходная матрица со значениями.
d[0][0] = a[0][0] ( попасть сюда можно одним путем - остаться в этой клетке ).
d[0][i] = d[0][i - 1] +a[0][i] - в крайние верхние клетки можно попасть только слева
d[i][0] = d[i - 1][0] + a[i][0] - в крайние левые клетки можно попасть только сверху.
d[i][i] = max( d[i - 1][j], d[i][j - 1] ) + a[i][j] - можно прийти слева и сверху, из двух вариантов выбирается максимальный.
Ну и препятствия учесть.
Ланселот, для начинающих. Это очень простая динамика.
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
03.11.2011, 22:07 9
Если по быстрому решать то так:
имеем массив char mas[n][m], заполненный такими значениями:
0044x
300x7
00100
создаем свой массив a[n][m] заполненный значениями -1,
далее так:
C++
1
2
3
4
5
6
7
8
9
10
11
a[0][0]=(int)(mas[0][0]-'0');
for(int i=1; i<m; i++)
   if(mas[0][i]!='x')
        a[0][i]=a[0][i-1]+(int)(mas[0][i]-'0');
   else
        break;
for(int i=1; i<n; i++)
   if(mas[i][0]!='x')
        a[i][0]=a[i-1][0]+(int)(mas[i][0]-'0');
   else
        break;
Дальше так:
C++
1
2
3
4
for(i=1; i<n; i++)
    for(j=1; j<m; j++)
        if((a[i][j-1]!=-1 || a[i-1][j]!=-1) && mas[i][j]!='x')
            a[i][j]=max(a[i][j-1], a[i-1][j])+(int)(mas[i][j]-'0');
Выводим a[n-1][m-1]
Еще не учел вариант когда mas[i][j]=='x' - можно в этом случае отдельно вывести -1
1
Higher
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
03.11.2011, 22:15 10
Лучший ответ Сообщение было отмечено как решение

Решение

Не тестировал, но примерно так:
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
#include <iostream>
#include <vector>
 
int main()
{
    int n, m;
    std::cin >> n >> m;
    std::vector< std::vector< char > > matrix(n, std::vector< char > (m) );
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            std::cin >> matrix.at(i).at(j);
    
    std::vector< std::vector< int > > dinamic(n, std::vector< int > (m, -1) );
    dinamic.at(0).at(0) = matrix.at(0).at(0) - '0';
    for ( int i = 0; i < n ; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if ( i == 0 && j == 0 )
                continue;
            
            if ( matrix[i][j] == 'x' )
                continue;
                
            if ( i > 0 && dinamic[i - 1][j] != -1 )
                dinamic[i][j] = dinamic[i - 1][j] + matrix[i][j] - '0';
            if ( j > 0 && dinamic[i][j - 1] != -1 )
                dinamic[i][j] = std::max( dinamic[i][j], dinamic[i][j - 1] + matrix[i][j] - '0' );
        }
        
    }
    
    std::cout << dinamic[n - 1][m - 1];     
}
3
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
03.11.2011, 22:24 11
diagon, Тоже не тестировал, но вижу пробелы:

Цитата Сообщение от diagon Посмотреть сообщение
if ( i > 0 && dinamic[i - 1][j] != -1 )
dinamic[i][j] = dinamic[i - 1][j] + matrix[i][j] - '0';
если matrix[i-1][0]=='x' (при j==0), а соответственно dinamic[i - 1][0]==-1, то dinamic[i][0] будет иметь значение отличное от -1
то же самое и для:

Цитата Сообщение от diagon Посмотреть сообщение
if ( j > 0 && dinamic[i][j - 1] != -1 )
dinamic[i][j] = std::max( dinamic[i][j], dinamic[i][j - 1] + matrix[i][j] - '0' );
0
5 / 5 / 2
Регистрация: 21.03.2011
Сообщений: 79
03.11.2011, 22:44  [ТС] 12
а как убедится, что маршрута не существует?
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
03.11.2011, 22:59 13
diagon, очень сильно извиняюсь перед Вами, но Ваш код правильный полностью (это я его не совсем рассмотрел - есть причины).
Montanaa, в коде diagon вычисляется все полнстью и в том числе, если маршрута не существует.
1
5 / 5 / 2
Регистрация: 21.03.2011
Сообщений: 79
03.11.2011, 23:05  [ТС] 14
Вывожу SEE YOU LATER если маршрута не существует. почему то не правильно работает
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
03.11.2011, 23:06 15
Montanaa, показывайте весь код.
1
5 / 5 / 2
Регистрация: 21.03.2011
Сообщений: 79
03.11.2011, 23:10  [ТС] 16
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Montanaa, показывайте весь код.
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
#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
        int n, m;
        cin >> n >> m;
 
    vector<vector<char>> arr(n, vector<char> (m));
        for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> arr[i][j];
     
    vector<vector<int>> z(n, vector<int> (m, - 1));
        z[0][0] = arr[0][0] - '0';
        for (int i = 0; i < n ; ++i)
        {
        for (int j = 0; j < m; ++j)
        {
            if (i == 0 && j == 0)
                continue;
                
                if (arr[i][j] == '*')
                    continue;
                
                if (i > 0 && z[i - 1][j] != -1)
                    z[i][j] = z[i - 1][j] + arr[i][j] - '0';
 
                if (j > 0 && z[i][j - 1] != -1)
                    z[i][j] = max(z[i][j], z[i][j - 1] + arr[i][j] - '0');
            }
        }
        
        if (z[n - 1][m - 1])
            cout << z[n - 1][m - 1] << endl;
        else
            cout << "SEE YOU LATER" << endl;
 
        return 0;
}
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
03.11.2011, 23:15 17
Цитата Сообщение от Montanaa Посмотреть сообщение
if (z[n - 1][m - 1])
cout << z[n - 1][m - 1] << endl;
else
cout << "SEE YOU LATER" << endl;
заменить на:
C++
1
2
3
4
if (z[n - 1][m - 1]!=-1)
 cout << z[n - 1][m - 1] << endl;
 else
 cout << "SEE YOU LATER" << endl;
1
03.11.2011, 23:15
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.11.2011, 23:15
Помогаю со студенческими работами здесь

Определить может ли король добраться из клетки x1 y1 в клетку x2 y2 за 1 ход
2 задача.Требуется вывести 1 если король сможет добраться из клетки x1 y1 в клетку x2 y2 за 1 ход...

Может ли шахматный ферзь за один ход перейти с клетки в клетку
Заданы координаты клетки шахматной доски (х; у) - целые числа. Выяснить, может ли шахматный ферзь...

Создать запись в клетку ссылки на другую клетку, запись в клетку функции суммирования блока клеток
Ребят, подскажите- только начала изучать программу, создала таблицу, не получается создать запись в...

Найти такой путь из клетки (1,1) в клетку (А, В), чтобы сумма чисел равнялась заданному числу К
Помогите написать программу к задаче Дано шахматную доску размером М на N. Шахматная фигура...

Найти такой путь из клетки [i1, j1] в клетку [i2, j2], чтобы сумма чисел по данному пути была минимальной
Здравствуйте, есть такая задача: 1.Дан двумерный числовой массив размером N1xN2. 2.Найти такой...

Найти путь из клетки (1, 1) в клетку (N, N), чтобы сумма цифр в клетках, через которые он пролегает, была минимальной
В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из...


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

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru