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

Задача Ход конем - 2. - C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.86
neske
1426 / 793 / 56
Регистрация: 26.03.2010
Сообщений: 2,734
12.10.2011, 20:33     Задача Ход конем - 2. #1
день добрый.
задача: http://informatics.mccme.ru/moodle/m...apterid=2962#1

как видите, задача на тему дп, но я смог решить только с помощью рекурсии. Система решение приняло, но всеравно оно мне не особо нравится, долго работает на данных побольше. Хотел узнать, как решить ее с помощью дп.

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <fstream>
#include <iostream>
 
bool possible (const int, const int, const int);
void rec (const int, const int);
 
const int size = 15;
int arr[size][size] = {0}, Row, Column;
 
int main() {
    std::ifstream ifs ("input.txt");
    std::ofstream ofs ("output.txt");
    //
    std::cin >> Row >> Column;
 
    if ((Row + Column) < 5) { //т.к. ход конем не сделать.
        std::cout << 0;
        return 0;
    }
    arr[0][0] = 1;
    //
    rec (0, 0);
    //
    std::cout << arr[Row - 1][Column - 1];
    //
    ifs.close();
    ofs.close();
    return 0;
}
 
bool possible (const int course, const int cur_i, const int cur_j) {
    // не выйдем ли мы за границы, если пойдем из клетки (i, j) ходом course.
    switch (course) { // course - 1 из 4 видов ходов (из рисунка по ссылке).
        case 1:
            return ((cur_i > 0) && (cur_j < Column - 2));
            break;
        case 2:
            return ((cur_i < Row - 1) && (cur_j < Column - 2));
            break;
        case 3:
            return ((cur_i < Row - 2) && (cur_j < Column - 1));
            break;
        case 4:
            return ((cur_i < Row - 2) && (cur_j > 0));
            break;
        default:
            return 0;
    }
}
 
void rec (const int i, const int j) {
    if ((i == Row - 1) && (j == Column - 1)) // если на последней клетке - 
        return;                              // дальше ходить не нужно.
 
    if (possible (1, i, j)) { 
        arr[i - 1][j + 2] += arr[i][j];
        rec (i - 1, j + 2);
    }
    if (possible (2, i, j)) {
        arr[i + 1][j + 2] += arr[i][j];
        rec (i + 1, j + 2);
    }
    if (possible (3, i, j)) {
        arr[i + 2][j + 1] += arr[i][j];
        rec (i + 2, j + 1);
    }
    if (possible (4, i, j)) {
        arr[i + 2][j - 1] += arr[i][j];
        rec (i + 2, j - 1);
    }
    arr[i][j] = 0; 
 
    return;
}
Спасибо.

Добавлено через 2 часа 4 минуты
Ап, ап.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.10.2011, 20:33     Задача Ход конем - 2.
Посмотрите здесь:

СИ++ ход конем C++
C++ Обход доски шахматным конем
Шахматы: определение правильности хода конем C++
C++ Ход конем
Обход шахматной доски конем C++
Задача "Тур конем" C++
C++ Шаг конем
C++ Ход конем до конкретной точки
C++ Рекурсия. Ход конем
C++ Почему происходит ошибка времени выполнения в решении задачи "Ход конем"?
C++ Ход конем
Обход доски конем C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.10.2011, 22:14     Задача Ход конем - 2. #2
neske, для меня из рисунка к условию задачи видится такая динамика:
- создаем массив mas[N][M], обнуляем все элементы массива, элементу mas[0][0] присваиваем значение 1
- затем начиная с верхнего левого угла массива (с mas[0][0]) идем по побочным диагоналям массива (без разницы сверху справа - вниз налево или наоборот). Если встречаем значение отличное от 0, то согласно рисунка прибавляем это значение к четырем другим элементам (куда может ходить конь, естественно учитываем границы массива).
- по прохождении таким образом массива в mas[N-1][M-1] будет наш результат.
neske
1426 / 793 / 56
Регистрация: 26.03.2010
Сообщений: 2,734
12.10.2011, 22:54  [ТС]     Задача Ход конем - 2. #3
о, и правда! а ведь нужно было внимательно посмотреть на рисунок, и придумать, как обходить. спасибо)
Yandex
Объявления
12.10.2011, 22:54     Задача Ход конем - 2.
Ответ Создать тему
Опции темы

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