Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/8: Рейтинг темы: голосов - 8, средняя оценка - 5.00
DaddySam22
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 13
1

Попасть шахматным конем в заданную клетку поля за наименьшее число ходов

14.12.2015, 14:26. Просмотров 1474. Ответов 11
Метки нет (Все метки)

На шахматной доске NxN в клетке (x1, y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2, y2), где растет вкусная шахматная трава. Какое наименьшее количество ходов он должен для этого сделать?

Входные данные
На вход программы поступает пять чисел: N, x1, y1, x2, y2 (5 <= N <= 20, 1 <= x1, y1, x2, y2 <= N). Левая верхняя клетка доски имеет координаты (1, 1), правая нижняя - (N, N).

Выходные данные
В первой строке выведите единственное число K - наименьшее необходимое число ходов коня. В каждой из следующих K+1 строк должно быть записано 2 числа - координаты очередной клетки в пути коня.

Помогите найти ошибку,код по идее правильный.
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream> 
 
using namespace std; 
 
int main() 
{ 
    int A[30][30]; 
    int B[30][30][3]; 
    int a,b,c,n,k1,k2,d1,d2; 
    cin>>n; 
    cin>>k1; 
    cin>>d1; 
    cin>>k2; 
    cin>>d2;
    
    for(a=2;a<n+2;a++) 
    {
        for(b=2;b<n+2;b++) 
        {
            A[a][b]=0;
        }
    }
    
    A[k1][k2]=1;
    
    for(c=0;c<100;c++) 
    { 
        for(a=1;a<n+2;a++) 
        {
            for(b=3;b<n+2;b++) 
            {
                if(A[a][b]>0&&(A[a+2][b+1]>A[a][b]+1||A[a+2][b+1]==0)) 
                {
                    A[a+2][b+1]=A[a][b]+1; 
                    B[a+2][b+1][1]=a; 
                    B[a+2][b+1][2]=b;
                } 
                if(A[a][b]>0&&(A[a+1][b+2]>A[a][b]+1||A[a+1][b+2]==0)) 
                {
                    A[a+1][b+2]=A[a][b]+1; 
                    B[a+1][b+2][1]=a; 
                    B[a+1][b+2][2]=b;
                } 
                if(A[a][b]>0&&(A[a+2][b-1]>A[a][b]+1||A[a+2][b-1]==0)) 
                {   
                    A[a+2][b-1]=A[a][b]+1; 
                    B[a+2][b-1][1]=a; 
                    B[a+2][b-1][2]=b;
                } 
                if(A[a][b]>0&&(A[a+1][b-2]>A[a][b]+1||A[a+1][b-2]==0)) 
                {
                    A[a+1][b-2]=A[a][b]+1; 
                    B[a+1][b-2][1]=a; 
                    B[a+1][b-2][2]=b;
                } 
                if(A[a][b]>0&&(A[a-2][b-1]>A[a][b]+1||A[a-2][b-1]==0)) 
                {
                    A[a-2][b-1]=A[a][b]+1; 
                    B[a-2][b-1][1]=a; 
                    B[a-2][b-1][2]=b;
                } 
                if(A[a][b]>0&&(A[a-1][b-2]>A[a][b]+1||A[a-1][b-2]==0)) 
                {
                    A[a-1][b-2]=A[a][b]+1; 
                    B[a-1][b-2][1]=a; 
                    B[a-1][b-2][2]=b;
                } 
                if(A[a][b]>0&&(A[a+1][b-2]>A[a][b]+1||A[a+1][b-2]==0)) 
                {
                    A[a+1][b-2]=A[a][b]+1; 
                    B[a+1][b-2][1]=a; 
                    B[a+1][b-2][2]=b;
                } 
                if(A[a][b]>0&&(A[a-2][b+1]>A[a][b]+1||A[a-2][b+1]==0)) 
                {
                    A[a-2][b+1]=A[a][b]+1; 
                    B[a-2][b+1][1]=a; 
                    B[a-2][b+1][2]=b;
                } 
                if(A[a][b]>0&&(A[a-1][b+2]>A[a][b]+1||A[a-1][b+2]==0)) 
                {
                    A[a-1][b+2]=A[a][b]+1; 
                    B[a-1][b+2][1]=a; 
                    B[a-1][b+2][2]=b;
                }
            }
        }
    }
    
    cout<<A[k2][d2+2]-1<<endl; 
    b=B[k2][d2+2][1]; 
    c=B[k2][d2+2][2];
    
    for(a=5;a>0;a--) 
    {
        if(b==k2&&c==d2+2) 
        {
            a=0;
        } 
        else 
        {
            cout<<B[b][c][1]<<" "<<B[b][c][2]; 
            cout<<endl; 
            b=B[b][c][1]; 
            c=B[b][c][2];
        }
    } 
     
    system("Pause"); 
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.12.2015, 14:26
Ответы с готовыми решениями:

Какое наименьшее количество ходов должен сделать конь, чтобы попасть на заданную клетку
На шахматной доске NxN в клетке (x1, y1) стоит голодный шахматный конь. Он...

Определить поля в которые может попасть конь за n ходов из указанной позиции
помогите, пожалуйста!!! на шахматной доске определить поля в которые может...

На шахматной доске определить поля, в которые может попасть конь за n ходов из указанной позиции (рекурсия)
На шахматной доске определить поля, в которые может попасть конь за n ходов из...

Обход доски шахматным конем
решал задачу &quot;Тур конем&quot;. : На шахматной доске размером n*n на поле с...

Наименьшее количество ходов для прохождения игры, алгоритм Дейкстры
Есть игра. Она собой представляет прямую линию. Цель игры достаться от начала в...

11
Doctor_
236 / 235 / 142
Регистрация: 03.02.2011
Сообщений: 1,436
14.12.2015, 14:31 2
Это Java? Нет.
0
DaddySam22
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 13
14.12.2015, 14:47  [ТС] 3
Это код с++,не в тот раздел случайно отправил
0
_Ivana
3236 / 1868 / 235
Регистрация: 01.03.2013
Сообщений: 5,111
Записей в блоге: 5
15.12.2015, 00:54 4
Нерекурсивный поиск в ширину на самодельном велосипедном стеке в рекурсивной по сути задаче... Три вложенных цикла... Не знаю, краснеть или нет, Кнут такое вроде даже приветствовал. Аксептед все тесты.
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
#include <iostream>
using namespace std;
 
typedef struct {int x; int y; int p;} step;
 
void show(step *sts, int i) {
    if (i>0) {show(sts, sts[i].p); cout<<sts[i].x<<" "<<sts[i].y<<'\n';}}
 
int main() {
    const int N=20, dx[]={1,2,2,1,-1,-2,-2,-1}, dy[]={2,1,-1,-2,-2,-1,1,2};
    int w[N+1][N+1]={0,}, b=0, e=0, isolve=0, added=0, cnt=0;   
    step sts[N*N]; sts->p=-1; 
    int n, x2, y2; cin >> n >> sts->x >> sts->y >> x2 >> y2;
   
    do {added=0; int ic=e+1;
        for (int i=b; i<=e && !isolve; ++i)
        for (int j=0; j<8; ++j) {
            int x = sts[i].x + dx[j], y = sts[i].y + dy[j];
            if (x<1 || y<1 || x>n || y>n || w[x][y]) continue;
            
            w[x][y]++; added=1;
            step *s=sts+(ic++); s->x=x; s->y=y; s->p=i;
            if (x==x2 && y==y2) {isolve=ic-1; break;}
        }
        cnt++; b=e+1; e=ic-1;
    } while (!isolve && added);
    
    if (isolve) cout<<cnt<<'\n'; else cout<<"no solutions\n";
    show(sts, isolve);
}
1
DaddySam22
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 13
15.12.2015, 11:32  [ТС] 5
_Ivana, Нужно,чтоб после наименьшего числа, шли первые координаты точки, в которой стоит конь,а дальше уже его каждый шаг
0
Mr.X
Эксперт С++
3183 / 1710 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
15.12.2015, 12:08 6
Была уже такая задачка.
0
DaddySam22
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 13
15.12.2015, 12:22  [ТС] 7
Mr.X, нет,там слишком большая и многое еще как бы не должен знать я по программе
0
Dimension
Dimension
574 / 444 / 221
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
15.12.2015, 12:55 8
на сайте же есть разбор
0
_Ivana
3236 / 1868 / 235
Регистрация: 01.03.2013
Сообщений: 5,111
Записей в блоге: 5
15.12.2015, 15:33 9
Да все уже было в Симпсонах

DaddySam22 кому нужно, тот сам своего коня объезжает.

Добавлено через 1 минуту
Dimension хорошо бы указывать хотя бы название сайта, если прямы ссылки запрещены. А то их много.
0
DaddySam22
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 13
15.12.2015, 17:08  [ТС] 10
_Ivana, конь то мой , но вот Ваш код я с трудом разбираю, и не знаю где нужно изменить первую точку
0
_Ivana
3236 / 1868 / 235
Регистрация: 01.03.2013
Сообщений: 5,111
Записей в блоге: 5
15.12.2015, 17:21 11
DaddySam22, 2 варианта:
1) для халявщиков - просто вписать стартовое поле коня (вы же его знаете) перед выводом ходов
2) для ковбоев - разобраться в коде и изменить один символ, чтобы выводилась стартовая клетка
0
DaddySam22
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 13
15.12.2015, 19:02  [ТС] 12
_Ivana, можете все же сказать,где заменить надо,пожалуйста?

Добавлено через 37 минут
_Ivana, все,не надо ,спасибо
0
15.12.2015, 19:02
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.12.2015, 19:02

Необходимо написать программу обхода конем всего шахматного поля
Доброго времени суток! Необходимо написать программу обхода конем всего...

Определить последовательность ходов, которая позволит обойти все поля и вернуться на исходную.
Помогите решить задачу... Очень сильно нужно!! Задача: Вводится начальная...

Какую наибольшую стоимость может иметь путь из клетки (1, 1) в клетку (n, m), если передвигаться за 1 шаг можно только на правую или нижнюю клетку.
кому не трудно помогите сделать. если не трудно вам написать код. Дана...


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

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

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