Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.86
neske
1503 / 870 / 84
Регистрация: 26.03.2010
Сообщений: 2,985
#1

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

12.10.2011, 20:33. Просмотров 4228. Ответов 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 минуты
Ап, ап.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.10.2011, 20:33
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача Ход конем - 2. (C++):

СИ++ ход конем - C++
Добрый вечер. Я начинающий в Си++, даже очень. Т.к. лекций в универе по си++ теперь(раньше были по си) нет, то толком ничего не понятно. ...

Ход конем - C++
На шахматной доске (8х8) стоят конь и пешка. Конь располагается на поле А, пешка - на поле B. Найти минимальное количество ходов, за...

Ход конем - C++
Совсем недавно Вася занялся программированием и решил реализовать собственную программу для игры в шахматы. Но у него возникла проблема...

Рекурсия. Ход конем - C++
написал код на &quot;КОНЯ&quot; ))) ( рекурсия ) а она чего-то все ходы не просчитывает.??? #include &lt;iostream&gt; #include &lt;stdlib.h&gt; ...

Ход конем до конкретной точки - C++
написал такую программу.конь обходит доску. как изменить его так чтоб он дошел до конкретной точки которую опчть по функции rand мы найдем...

Почему происходит ошибка времени выполнения в решении задачи "Ход конем"? - C++
Добрый день! Я попытался решить одну задачку о шахматах. Проблема в том, что моя программа крашится с такой ошибкой: ...

2
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.10.2011, 22:14 #2
neske, для меня из рисунка к условию задачи видится такая динамика:
- создаем массив mas[N][M], обнуляем все элементы массива, элементу mas[0][0] присваиваем значение 1
- затем начиная с верхнего левого угла массива (с mas[0][0]) идем по побочным диагоналям массива (без разницы сверху справа - вниз налево или наоборот). Если встречаем значение отличное от 0, то согласно рисунка прибавляем это значение к четырем другим элементам (куда может ходить конь, естественно учитываем границы массива).
- по прохождении таким образом массива в mas[N-1][M-1] будет наш результат.
2
neske
1503 / 870 / 84
Регистрация: 26.03.2010
Сообщений: 2,985
12.10.2011, 22:54  [ТС] #3
о, и правда! а ведь нужно было внимательно посмотреть на рисунок, и придумать, как обходить. спасибо)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.10.2011, 22:54
Привет! Вот еще темы с ответами:

Задача "Тур конем" - C++
На шахматной доске размером на поле с координатами х0, у0 находится конь – фигура, перемещающаяся по обычным шахматным правилам. Задача...

Шаг конем - C++
просьба . помогите . ну вот я должен написать код обход коня по всей доске ,программа находит первую точку коня и его первые возможные...

Обход доски конем - C++
Дана шахматная доска размером 8х8 и шахматный конь. Программа должна запросить у пользователя координаты клетки поля и поставить туда коня....

Обход доски шахматным конем - C++
решал задачу &quot;Тур конем&quot;. : На шахматной доске размером n*n на поле с координатами x0,y0 находится конь - фигура , перемещающаяся по...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

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