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

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

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

C++ за сколько ходов конь переместиться в указанные координаты
C++ Конь.
C++ Шахмотный конь
C++ Бьет ли конь пешку?
C++ Волновой алгоритм (шахматы, конь)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
x1Mike7x
 Аватар для x1Mike7x
214 / 127 / 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 "Точно угроза!!!"
I.M.
 Аватар для 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
daemonik
 Аватар для daemonik
3 / 3 / 0
Регистрация: 24.04.2010
Сообщений: 37
03.10.2012, 01:01  [ТС]     Шахматы, конь #4
Цитата Сообщение от x1Mike7x Посмотреть сообщение
3) Для каждого хода из предыдущих восьми проверяем еще восемь из каждой новой вершины
Вот именно это как запрограммировать я не понимаю.
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
03.10.2012, 01:01     Шахматы, конь #5
Цитата Сообщение от daemonik Посмотреть сообщение
Угрожает ли он полю (m, n)?
Кстати, это значит, что после двух ходов конь должен оказаться на этом поле или что после двух ходов на третий конь может оказаться на этом поле?
daemonik
 Аватар для daemonik
3 / 3 / 0
Регистрация: 24.04.2010
Сообщений: 37
03.10.2012, 01:02  [ТС]     Шахматы, конь #6
Цитата Сообщение от I.M. Посмотреть сообщение
Кстати, это значит, что после двух ходов конь должен оказаться на этом поле или что после двух ходов на третий конь может оказаться на этом поле?
Это значит, что его 3-ий ход может оказаться на этом поле.
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
03.10.2012, 01:09     Шахматы, конь #7
Цитата Сообщение от daemonik Посмотреть сообщение
Вот именно это как запрограммировать я не понимаю.
Делайте рекурсивный алгоритм
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.10.2012, 06:02     Шахматы, конь
Еще ссылки по теме:

Требуется определить, бьет ли конь C++
Конструктор и классы. Предметная область: «Конь на шахматной доске» C++
Шахматная фигура конь C++

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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;
}
Yandex
Объявления
03.10.2012, 06:02     Шахматы, конь
Ответ Создать тему
Опции темы

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