5 / 5 / 2
Регистрация: 21.03.2011
Сообщений: 79
|
|
1 | |
Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку.03.11.2011, 21:37. Показов 2674. Ответов 16
Метки нет (Все метки)
кому не трудно помогите сделать. если не трудно вам написать код.
Дана прямоугольная таблица 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
|
03.11.2011, 21:37 | |
Ответы с готовыми решениями:
16
Минимальный путь из левой верхней в правую нижнюю клетку таблицы. Сколько есть способов попасть в правую нижнюю клетку Сколько есть способов у игрока попасть в правую нижнюю клетку В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N |
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
|
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
|
|
03.11.2011, 22:00 | 8 |
Угу.
Алгоритм примерно такой: Завести матрицу 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, далее так:
Еще не учел вариант когда mas[i][j]=='x' - можно в этом случае отдельно вывести -1
1
|
Higher
|
||||||
03.11.2011, 22:15 | 10 | |||||
Сообщение было отмечено как решение
Решение
Не тестировал, но примерно так:
3
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
03.11.2011, 22:24 | 11 |
diagon, Тоже не тестировал, но вижу пробелы:
если matrix[i-1][0]=='x' (при j==0), а соответственно dinamic[i - 1][0]==-1, то dinamic[i][0] будет иметь значение отличное от -1 то же самое и для:
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 | |||||
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
03.11.2011, 23:15 | 17 | |||||
заменить на:
1
|
03.11.2011, 23:15 | |
03.11.2011, 23:15 | |
Помогаю со студенческими работами здесь
17
Определить может ли король добраться из клетки x1 y1 в клетку x2 y2 за 1 ход Может ли шахматный ферзь за один ход перейти с клетки в клетку Создать запись в клетку ссылки на другую клетку, запись в клетку функции суммирования блока клеток Найти такой путь из клетки (1,1) в клетку (А, В), чтобы сумма чисел равнялась заданному числу К Найти такой путь из клетки [i1, j1] в клетку [i2, j2], чтобы сумма чисел по данному пути была минимальной Найти путь из клетки (1, 1) в клетку (N, N), чтобы сумма цифр в клетках, через которые он пролегает, была минимальной Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |