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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 5.00
daemonik
3 / 3 / 0
Регистрация: 24.04.2010
Сообщений: 37
#1

Шахматы, конь - C++

03.10.2012, 00:34. Просмотров 2224. Ответов 7
Метки нет (Все метки)

Всем доброго времени суток! Буду честен - в универе задали задачу на макс.балл(все предыдущие сделал, но с этой возникла проблемка). Условие следующее: Поле шахматной доски определяется парой натуральных чисел (номер вертикали – номер горизонтали) из диапазона 1-8. Конь, расположенный на поле (k, l), делает 2 хода. Угрожает ли он полю (m, n)?
Собственно просьба: помогите составить сам алгоритм. Поскольку сам пока отмечал клеточки на листиках, ища закономерность, запутался. Закодить я сам смогу.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.10.2012, 00:34
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Шахматы, конь (C++):

Волновой алгоритм (шахматы, конь) - C++
Всем привет! Пытался написать волновой алгоритм для нахождения кратчайшего пути коня на шахматной доски из A->B. Но что-то у меня...

Конь. - C++
Здравствуйте! Опять обращаюсь за помощью, раньше уже обращался поп поводу этой задачи. Я сделал задачу про путешестиве коня более...

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

Бьет ли конь пешку? - C++
даны координаты коня и другой фигуры. вывести: бьет ли конь фигуру? как записать условие? вот что у меня получилось #include...

Шахматная фигура конь - C++
Шахматная фигура конь ходит на 1 клетку по горизонтали и на 2 клетки по вертикали или наоборот на 2 клетки по горизонтали и на 1 по...

Требуется определить, бьет ли конь - C++
Здравствуйте, уважаемые программисты! помоги пожалуйста решить задачку на Паскале. Условие задачи - Требуется определить, бьет ли конь,...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
x1Mike7x
217 / 130 / 6
Регистрация: 06.11.2010
Сообщений: 234
03.10.2012, 00:56 #2
1) Стоим себе в начальной точке.
2) Проверяем все возможные ходы коня ( всего 8 штук )
3) Для каждого хода из предыдущих восьми проверяем еще восемь из каждой новой вершины
4) Если хотя бы раз попадаем в нужную вершину, то выводим "Угрожаем".

Примерно так:
Код
x = k, y = l;
dx = [1, 1, 2, 2, -1, -1, -2, -2]
dy = [2, -2, 1, -1, 2, -2, 1, -1]
for i = 1..8:
    x1 = x + dx[i]
    y1 = y + dy[i]
    if x1 == n && y1 == m:
        print "Угроза!!!"
    for j = 1..8:
        x2 = x1 + dx[j]
        y2 = y1 + dy[j]
        if x2 == n && y2 == m:
            print "Точно угроза!!!"
0
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
03.10.2012, 00:57 #3
Составляете массив клеток, с которых конь может угрожать клетке (m,n). Таких клеток в общем случае будет 8. Соответственно, если (m,n) расположена где-то с краю или в углу, то их будет меньше 8.
А затем проходите по этому массиву и проверяете, достижима ли эта клетка коню за 1 ход или нет. Если хотя бы одна достижима, то возвращаете true. Если ни одна не достижима, то false
0
daemonik
3 / 3 / 0
Регистрация: 24.04.2010
Сообщений: 37
03.10.2012, 01:01  [ТС] #4
Цитата Сообщение от x1Mike7x Посмотреть сообщение
3) Для каждого хода из предыдущих восьми проверяем еще восемь из каждой новой вершины
Вот именно это как запрограммировать я не понимаю.
0
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
03.10.2012, 01:01 #5
Цитата Сообщение от daemonik Посмотреть сообщение
Угрожает ли он полю (m, n)?
Кстати, это значит, что после двух ходов конь должен оказаться на этом поле или что после двух ходов на третий конь может оказаться на этом поле?
0
daemonik
3 / 3 / 0
Регистрация: 24.04.2010
Сообщений: 37
03.10.2012, 01:02  [ТС] #6
Цитата Сообщение от I.M. Посмотреть сообщение
Кстати, это значит, что после двух ходов конь должен оказаться на этом поле или что после двух ходов на третий конь может оказаться на этом поле?
Это значит, что его 3-ий ход может оказаться на этом поле.
0
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
03.10.2012, 01:09 #7
Цитата Сообщение от daemonik Посмотреть сообщение
Вот именно это как запрограммировать я не понимаю.
Делайте рекурсивный алгоритм
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.10.2012, 06:02 #8
Цитата Сообщение от I.M. Посмотреть сообщение
Делайте рекурсивный алгоритм
можно рекурсией, можно с помощью очереди.
Вот здесь не самый оптимальный алгоритм (по времени), но для такого маленького поля и так пойдет:
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
#include <iostream>
using namespace std;
int main()
{
    int a[8][8]={0}, i, j, k, l, n, m, y;
    cout<<"k= "; cin>>k;
    cout<<"l= "; cin>>l;
    cout<<"m= "; cin>>m;
    cout<<"n= "; cin>>n;
    a[k-1][l-1]=1;
    for(y=1; y<3; y++)
    {
        for(i=0; i<8; i++)
            for(j=0; j<8; j++)
                if(a[i][j]==y)
                {
                    if(i>0)
                    {
                        if(j>1) a[i-1][j-2]=y+1;
                        if(j<6) a[i-1][j+2]=y+1;
                    }
                    if(i>1)
                    {
                        if(j>0) a[i-2][j-1]=y+1;
                        if(j<7) a[i-2][j+1]=y+1;
                    }
                    if(i<7)
                    {
                        if(j>1) a[i+1][j-2]=y+1;
                        if(j<6) a[i+1][j+2]=y+1;
                    }
                    if(i<6)
                    {
                        if(j>0) a[i+2][j-1]=y+1;
                        if(j<7) a[i+2][j+1]=y+1;
                    }
                }
    }
    if(a[m-1][n-1]==0)
        cout<<"No"<<endl;
    else
        cout<<"Yes"<<endl;
 return 0;
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.10.2012, 06:02
Привет! Вот еще темы с ответами:

Угрожает ли конь, стоящий на поле (k, l), полю (m, n) - C++
Поле шахматной доски определяется парой натуральных чисел, первое из которых задает номер вертикали, а второе — номер горизонтали. Даны...

За сколько ходов конь переместиться в указанные координаты - C++
Вводятся начальные и конечные координаты положения шахматного коня (x1, y1, x2, y2), написать программу, определяющую за сколько ходов ...

Конструктор и классы. Предметная область: «Конь на шахматной доске» - C++
Помогите написать прогу к этой задаче: Предметная область: «Конь на шахматной доске». Данные класса: координаты коня. Функции класса:...

Проверить не угрожает ли данный шахматный конь заданному полю - C++
Поле шахматной доски имеет размер 8 x 8. Клетки обозначены координатами, первая - номер по вертикале (слева на право),вторая - номер по...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
03.10.2012, 06:02
Ответ Создать тему
Опции темы

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