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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Вычислить значение выражения http://www.cyberforum.ru/cpp-beginners/thread365347.html
Народ помогите! значит такая задача , надо ввести число , и что бы оно считало данную формулу (прикрепил файл) на С 2.3 Создавайте темы с осмысленными и понятными названиями - это серьезно повышает шансы, что на ваш вопрос ответят. 3.3 Запрещено создавать темы с бессмысленными названиями вроде "Помогите!", "Вопрос" и т.п.
C++ счастливый билет Вводится шестизначное число .Определить является ли билет с этим номером счастливым ?с оптимизацией времени решения на турбо си!прошу помочь) http://www.cyberforum.ru/cpp-beginners/thread365344.html
C++ Некоторые немешающие жить но терзающие мозг вопросы
Учусь по учебнику Джесс Либерти и наткнулся на некоторые непонятки. 1. (примерно так) const Cat * const Function(const Cat * const p) { return p; } Здесь меня смущает второе слово const. Имхо оно не имеет никакого смысла, в то время как наличие остальных влияет (может влиять) на программу. 2. Cat * Family = new Cat;
C++ Не могу разобраться с указателями
Здраствуйте все вот короче мне задали задачки на Си написать вот они собствено : 1.Даны два массива, упорядоченных по возрастанию: А и B. Сформируйте массив C, состоящий из элементов массивов А и В, упорядоченный по возрастанию. 2.Даны два массива : А и B. Необходимо создать третий массив, в котором нужно собрать: - Элементы обоих массивов; - Общие элементы двух массивов; - Элементы...
C++ Найти максимальное число в строке, содержащей слова и числа http://www.cyberforum.ru/cpp-beginners/thread365313.html
Необходимо найти максимальное число в строке содержащие слова и числа (числа формата f) и поделить на все числа строки Заранее спасибо!!!
C++ Сортировка пузырьковая Привет всем!помогите отсортировать задачку. #include <iostream> #include <iomanip> using namespace std; int main() { const int v=10; double m,a; int Min=0; double sum=0.0; подробнее

Показать сообщение отдельно
neske
1473 / 840 / 74
Регистрация: 26.03.2010
Сообщений: 2,881

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

12.10.2011, 20:33. Просмотров 3868. Ответов 2
Метки (Все метки)

день добрый.
задача: 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 минуты
Ап, ап.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru