Найти минимальное число ходов, которые нужны шахматному коню

@marymap · Регистрация: 28.11.2016

Студворк — интернет-сервис помощи студентам

Даны обозначения двух полей шахматной доски (например, A5 и C2). Найти минимальное число ходов, которые нужны шахматному коню для перехода с первого поля на второе.

реализовать нужно через очередь,но я пока не могу представить,как это делать.Подскажите, пожалуйста, как она должна работать

@marymap · 04.10.2017, 13:01 **[ТС]**

MansMI,

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include "stdafx.h"
#include <iostream>
/* Помещаем в очередь исходное поле коня
          Пока ( не нашли )
            Выбираем из очереди первый элемент - клетку X,Y
            Если это элемент НЕ искомый
              то Клетки, достижимые из X,Y за ход коня
                 если не конечные
                 и еще не помеченные
                 помещаем в очередь и помечаем*/
const int n = 8;
using namespace std;
int Que[64][3];//очередь ходов
 
bool Marked[8][8];
int x, y;
int StepNumber=0;
int QueEnd;
int conv(char pos) {
    int start_position_j;
    if (pos == 'A')
    {
        start_position_j = 0;
    };
    if (pos == 'B')
    {
        start_position_j = 1;
    }
 
    if (pos == 'C')
    {
        start_position_j = 2;
    }
    if (pos == 'D')
    {
        start_position_j = 3;
    }
    if (pos == 'E')
    {
        start_position_j = 4;
    }
    if (pos == 'F')
    {
        start_position_j = 5;
    };
    if (pos == 'G')
    {
        start_position_j = 6;
    };
    if (pos == 'H')
    {
        start_position_j = 7;
    };
    return start_position_j;
};////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void Get(int StepNumber, int QueBegin) {//Взять из очереди
    x = Que[QueBegin][0];
    y = Que[QueBegin][1];
    StepNumber = Que[QueBegin][2];
    QueBegin++;
};
void Put(int x, int y, int QueEnd,int StepNumber) {//Занести в очередь
 
    Que[QueEnd][0] = x;
    Que[QueEnd][1] = y;
    Que[QueEnd][2] = StepNumber;
    Marked[x][y] = true;
    QueEnd++;
};
 
 
void PutAll(int x, int y, int end_position_j, int end_position_i, bool Found) {//Занести в очередь все текущие возможные ходы
    int Knight[8][2] = { {1,-2},{1, 2},{-1, -2},{-1, 2},{2, -1}, {2, 1},{-2, -1},{-2,1} };
    int i, CurrentX, CurrentY;
    Found = false;
    i = 0;
    while ((!Found) && (i < 8)) {
        
        CurrentX = x + Knight[i][0];
        CurrentY = y + Knight[i][1];
        i++;
        Found = ((end_position_j == CurrentX) && (end_position_i == CurrentY));
        if (!Found && (CurrentX > 0) && (CurrentX < 9) && (CurrentY > 0) && (CurrentY < 9) && !(Marked[CurrentX, CurrentY])) {
            Put(CurrentX, CurrentY,QueEnd,StepNumber);//помещаем в очередь и помечаем
        }
    }
};
int main()
{   bool Found;//пометки на доске
    char start_position_c, end_position_c;
    int start_position_i, end_position_i, start_position_j, end_position_j, QueBegin;
    cout << "enter last and end position : ";
    while ((!(cin >> start_position_c >> start_position_i >> end_position_c >> end_position_i)) || (start_position_c < 'A') || (start_position_c > 'H') ||
        (end_position_c < 'A') || (end_position_c > 'H') || (start_position_i < 1) || (start_position_i > 8) || (end_position_i < 1) || (end_position_i > 8)) {
        cin.clear();
        while (cin.get() != '\n');
        cout << "ERROR! ";
        cout << "enter again: ";
    }
    start_position_i--;
    end_position_i--;
    start_position_j = conv(start_position_c);
    end_position_j = conv(end_position_c);
    ////////
    QueBegin = 1;
    QueEnd = 0; 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            Marked[i][j] = false;
        }
    } Put(start_position_j, start_position_i, QueEnd, 0);
    //Начальную позицию в очередь
    /////////////////////////////////////////////////////////////////////////////////
    Marked[start_position_j][start_position_i] = true;
    Found = ((start_position_j == end_position_j) && (start_position_i == end_position_i));
    while (!Found){
        Get(StepNumber, QueBegin);
        StepNumber++;
        PutAll(start_position_j, start_position_i, end_position_j, end_position_i,Found); 
    }
        cout << StepNumber;
        system("pause");
        return 0;
}

@MansMI · 04.10.2017, 13:31

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
int a[8][8];
int amin[8][8];
int fx,fy;
int minstep=64;
int dx[]={-2,-2,-1,-1, 1,1, 2, 2};
int dy[]={-1, 1,-2, 2,-2,2,-1, 1};
void step(int x,int y,int nstep)
{
    if(nstep+1>=minstep) return;
    a[y][x]=++nstep;
    if(x==fx && y==fy) 
    {
        for(int i=0; i<8; i++)
            for(int j=0; j<8; j++) amin[i][j]=a[i][j];
        minstep=nstep;
        a[y][x]=0;
        return;
    }
    for(int i=0; i<8; i++)
    {
        int nx=x+dx[i];
        if(nx>=0 && nx<8)
        {
            int ny=y+dy[i];
            if(ny>=0 && ny<8 && !a[ny][nx]) step(nx,ny,nstep);
        }
    }
    a[y][x]=0;
}
void main(int argc,char **argv)
{
    int sx,sy;
    cout<<"Start X Y(0-7):";
    cin>>sx>>sy;
    cout<<"Finish X Y(0-7):";
    cin>>fx>>fy;
    for(int i=0; i<8; i++)
        for(int j=0; j<8; j++) a[i][j]=0;
    step(sx,sy,0);
    for(int i=7; i>=0; i--,cout<<endl)
        for(int j=0; j<8; j++) cout<<setw(3)<<amin[i][j];
    system("pause");
}

@Старый воин · 04.10.2017, 19:20

Доброго времени суток!
Вот, с помощью списка

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
#include "stdafx.h"
#include <iostream>
#include <queue>
#include <string>
 
using namespace std;
 
struct Cell
{
    int row;    //строка
    int column; //столбец
    int level;  //уровень хода
};
//начальная и конечная позиции коня
Cell *StartPosition, *EndPosition;
//очередь клеток доски, куда конь может сделать ход
queue <Cell> que;
 
//получить позицию
Cell *GetPosition(string str)
{
    Cell *tmp = new Cell;//создали новую клетку
    tmp->row = -1;//значения делаем отрицательными
    tmp->column = -1;//это нужно для проверок
    tmp->level = 0;//нулевой уровень (находимся в начальной точке)
    //проверим, что введены только 2 символа
    if (str.length() != 2)
    {
        cout << "Ошибка ввода" << endl;
        return tmp;
    }
    else
    {   //столбец
        switch (str[0])
        {
        case 'A':
            tmp->column = 0;
            break;
        case 'B':
            tmp->column = 1;
            break;
        case 'C':
            tmp->column = 2;
            break;
        case 'D':
            tmp->column = 3;
            break;
        case 'E':
            tmp->column = 4;
            break;
        case 'F':
            tmp->column = 5;
            break;
        case 'G':
            tmp->column = 6;
            break;
        case 'H':
            tmp->column = 7;
            break;
        default:
            cout << "Неверное значение столбца" << endl;
            return tmp;
            break;
        }
        //строка
        switch (str[1])
        {
        case '1':
            tmp->row = 0;
            break;
        case '2':
            tmp->row = 1;
            break;
        case '3':
            tmp->row = 2;
            break;
        case '4':
            tmp->row = 3;
            break;
        case '5':
            tmp->row = 4;
            break;
        case '6':
            tmp->row = 5;
            break;
        case '7':
            tmp->row = 6;
            break;
        case '8':
            tmp->row = 7;
            break;
        default:
            cout << "Неверное значение строки" << endl;
            return tmp;
            break;
        }
        return tmp;
    }
}
//проверка выхода за границу доски
bool TestPosition(int row, int column)
{
    if (((row >= 0) && (row <= 7)) && ((column >= 0) && (column <= 7)))
        return true;
    else
        return false;
}
//проверка клеток на совпадение
bool TestEnd(Cell *source, Cell *destination)
{
    if ((source->row == destination->row) && (source->column == destination->column))
        return true;
    else
        return false;
}
 
//Генерируем 8 позиций коня (ход из заданной клетки)
int Step(Cell *cel)
{
    int row = cel->row;
    int col = cel->column;
    int row_new;
    int col_new;
    //1 клетка
    row_new = row - 2;  //установка номера строки
    col_new = col + 1;  //установка номера клетки
    if (TestPosition(row_new, col_new))
    {
        Cell *tmp = new Cell;   //создаем ячейку и заполняем данными
        tmp->row = row_new;
        tmp->column = col_new;
        tmp->level = cel->level + 1;//изменяем уровень хода
        //проверка на совпадение с целевой клеткой
        if (TestEnd(EndPosition, tmp))
        {
            return tmp->level;//если совпадение, возвращаем ответ (мин. число ходов)
        }
        else
        {
            que.push(*tmp);//иначе, заносим клетку в очередь
        }
    }
    //2 клетка
    row_new = row - 1;  //установка номера строки
    col_new = col + 2;  //установка номера клетки
    if (TestPosition(row_new, col_new))
    {
        Cell *tmp1 = new Cell;  //создаем ячейку и заполняем данными
        tmp1->row = row_new;
        tmp1->column = col_new;
        tmp1->level = cel->level + 1;//изменяем уровень хода
        //проверка на совпадение с целевой клеткой
        if (TestEnd(EndPosition, tmp1))
        {
            return tmp1->level;//если совпадение, возвращаем ответ (мин. число ходов)
        }
        else
        {
            que.push(*tmp1);//иначе, заносим клетку в очередь
        }
    }
    //3 клетка
    row_new = row + 1;  //установка номера строки
    col_new = col + 2;  //установка номера клетки
    if (TestPosition(row_new, col_new))
    {
        Cell *tmp2 = new Cell;  //создаем ячейку и заполняем данными
        tmp2->row = row_new;
        tmp2->column = col_new;
        tmp2->level = cel->level + 1;//изменяем уровень хода
        //проверка на совпадение с целевой клеткой
        if (TestEnd(EndPosition, tmp2))
        {
            return tmp2->level;//если совпадение, возвращаем ответ (мин. число ходов)
        }
        else
        {
            que.push(*tmp2);//иначе, заносим клетку в очередь
        }
    }
    //4 клетка
    row_new = row + 2;  //установка номера строки
    col_new = col + 1;  //установка номера клетки
    if (TestPosition(row_new, col_new))
    {
        Cell *tmp3 = new Cell;  //создаем ячейку и заполняем данными
        tmp3->row = row_new;
        tmp3->column = col_new;
        tmp3->level = cel->level + 1;//изменяем уровень хода
        //проверка на совпадение с целевой клеткой
        if (TestEnd(EndPosition, tmp3))
        {
            return tmp3->level;//если совпадение, возвращаем ответ (мин. число ходов)
        }
        else
        {
            que.push(*tmp3);//иначе, заносим клетку в очередь
        }
    }
    //5 клетка
    row_new = row + 2;  //установка номера строки
    col_new = col - 1;  //установка номера клетки
    if (TestPosition(row_new, col_new))
    {
        Cell *tmp4 = new Cell;  //создаем ячейку и заполняем данными
        tmp4->row = row_new;
        tmp4->column = col_new;
        tmp4->level = cel->level + 1;//изменяем уровень хода
        //проверка на совпадение с целевой клеткой
        if (TestEnd(EndPosition, tmp4))
        {
            return tmp4->level;//если совпадение, возвращаем ответ (мин. число ходов)
        }
        else
        {
            que.push(*tmp4);//иначе, заносим клетку в очередь
        }
    }
    //6 клетка
    row_new = row + 1;  //установка номера строки
    col_new = col - 2;  //установка номера клетки
    if (TestPosition(row_new, col_new))
    {
        Cell *tmp5 = new Cell;  //создаем ячейку и заполняем данными
        tmp5->row = row_new;
        tmp5->column = col_new;
        tmp5->level = cel->level + 1;//изменяем уровень хода
        //проверка на совпадение с целевой клеткой
        if (TestEnd(EndPosition, tmp5))
        {
            return tmp5->level;//если совпадение, возвращаем ответ (мин. число ходов)
        }
        else
        {
            que.push(*tmp5);//иначе, заносим клетку в очередь
        }
    }
    //7 клетка
    row_new = row - 1;  //установка номера строки
    col_new = col - 2;  //установка номера клетки
    if (TestPosition(row_new, col_new))
    {
        Cell *tmp6 = new Cell;  //создаем ячейку и заполняем данными
        tmp6->row = row_new;
        tmp6->column = col_new;
        tmp6->level = cel->level + 1;//изменяем уровень хода
        //проверка на совпадение с целевой клеткой
        if (TestEnd(EndPosition, tmp6))
        {
            return tmp6->level;//если совпадение, возвращаем ответ (мин. число ходов)
        }
        else
        {
            que.push(*tmp6);//иначе, заносим клетку в очередь
        }
    }
    //8 клетка
    row_new = row - 2;  //установка номера строки
    col_new = col - 1;  //установка номера клетки
    if (TestPosition(row_new, col_new))
    {
        Cell *tmp7 = new Cell;  //создаем ячейку и заполняем данными
        tmp7->row = row_new;
        tmp7->column = col_new;
        tmp7->level = cel->level + 1;//изменяем уровень хода
        //проверка на совпадение с целевой клеткой
        if (TestEnd(EndPosition, tmp7))
        {
            return tmp7->level;//если совпадение, возвращаем ответ (мин. число ходов)
        }
        else
        {
            que.push(*tmp7);//иначе, заносим клетку в очередь
        }
    }
    return 0;
}
 
int main()
{
    setlocale(LC_ALL, "Russian");
    string str;
    cout << "Введите начальную позицию: ";
    getline(cin, str);
    StartPosition = GetPosition(str);
    cout << "Введите конечную позицию: ";
    getline(cin, str);
    EndPosition = GetPosition(str);
    //проверяем, может мы уже находимся в этой клетке?
    if (TestEnd(StartPosition, EndPosition))
    {
        cout << "End" << endl;
        return 0;
    }
    //делаем первый ход и заполняем очередь
    int result = Step(StartPosition);
    //проверяем, может уже дошли до цели?
    if (result != 0)
    {
        cout << result << endl;
        return 0;
    }
    //пока список не пуст, выполняем
    while (!que.empty())
    {   //делаем ход с очередной клетки
        result = Step(&que.front());
        if (result != 0)
        {
            cout << result << endl;
            return 0;
        }
        que.pop();//удаляем из очереди обработанную клетку
    }
    return 0;
}

Вроде бы работает. Поздно наверное уже. Но все, как еще один вариант решения.

@AlexVRud · 04.10.2017, 23:13

По мне, так решение должно выглядеть так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
size_t calculateKnightWay(Position start, Position finish, size_t size) {
  Board board(size);
  std::queue<QueueItem> queue;
  QueueItem current{0, start};
  while (current.position != finish) {
    auto new_positions = getNewPosotions(current.position, size);
    for (const auto &pos : new_positions) {
      if (board[pos] == SquareState::NotVisited) {
        board[pos] = SquareState::Visited;
        queue.push({current.numSteps + 1, pos});
      }
    }
    if (queue.empty())
      throw std::runtime_error("Can't find way");
    current = queue.front();
    queue.pop();
  }
  return current.numSteps;
}

Кликните здесь для просмотра всего текста

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
#include <iostream>
#include <queue>
#include <stdexcept>
#include <stdint.h>
#include <utility>
#include <vector>
 
enum class SquareState { NotVisited, Visited };
 
struct Position {
  size_t row;
  size_t col;
};
 
bool operator!=(const Position &l, const Position &r) {
  return (l.row != r.row) || (l.col != r.col);
}
 
class Board {
public:
  Board(size_t size)
      : m_size(size), m_data(size * size, SquareState::NotVisited){};
 
  SquareState &operator[](const Position &position) {
    return m_data[position.row * m_size + position.col];
  };
 
private:
  size_t m_size;
  std::vector<SquareState> m_data;
};
 
struct QueueItem {
  size_t numSteps;
  Position position;
};
 
std::vector<Position> getNewPosotions(const Position &position, size_t size) {
  static const std::vector<std::pair<int32_t, int32_t>> diffs = {
      {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}}};
  std::vector<Position> result;
  for (auto d : diffs) {
    int32_t y = (int32_t)position.row + d.first;
    int32_t x = (int32_t)position.col + d.second;
    if ((x >= 0) && (y >= 0) && (x < (int32_t)size) && (y < (int32_t)size))
      result.push_back({(size_t)y, (size_t)x});
  }
  return result;
}
 
size_t calculateKnightWay(Position start, Position finish, size_t size) {
  Board board(size);
  std::queue<QueueItem> queue;
  QueueItem current{0, start};
  while (current.position != finish) {
    auto new_positions = getNewPosotions(current.position, size);
    for (const auto &pos : new_positions) {
      if (board[pos] == SquareState::NotVisited) {
        board[pos] = SquareState::Visited;
        queue.push({current.numSteps + 1, pos});
      }
    }
    if (queue.empty())
      throw std::runtime_error("Can't find way");
    current = queue.front();
    queue.pop();
  }
  return current.numSteps;
}
 
int main() {
  std::cout << calculateKnightWay({'A' - 'A', 5 - 1}, {'C' - 'A', 2 - 1}, 8)
            << "\n";
  return 0;
}

Добавлено через 3 часа 32 минуты
Хотя не критично для решения, но я забыл сразу пометить стартовую точку как проверенную

C++
1
2
  Board board(size);
  board[start] = SquareState::Visited;

@Старый воин · 05.10.2017, 00:20

AlexVRud, красиво!

@MansMI · 05.10.2017, 08:05

Сообщение от marymap

например, A5 и C2

ну так какое решение?
у меня так:

Новые блоги и статьи Все статьи Все блоги /
Генератор паролей (вариант №4) Maks 01.11.2026 После публикации 3-го варианта генератора паролей, разослал его своим коллегам (с целью оценки), в итоге были получены следующие рекомендации: 1. Вернуть возможность использования знаков \| 1 l I;. . .	Генератор паролей (вариант №3) Maks 30.10.2026 Финальная версия генератора паролей 1С. Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты:. . .	Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени) zorxor 30.10.2026 Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию? Фраза «Любая достаточно развитая технология неотличима от магии». . .	За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ) zorxor 30.10.2026 Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль? Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .
Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени) zorxor 30.10.2026 Как убивали Suno. Хронология. «Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .	Генератор паролей (вариант №2) Maks 30.10.2026 Обновленная версия ранее созданной обработки. Добавлены следующие реквизиты типа Булево: - Буквы; - Цифры; - Символы. Изменена логика команды "Сгенерировать" и процедуры "ПриОткрытии":. . .	Генератор паролей (вариант №1) Maks 29.10.2026 Реализация из решения ниже выполнена исключительно по моей инициативе, дабы облегчить себе работу в создании паролей для администрируемых мною сервисов и пользователей. Самым главным критерием для. . .	Установка ChatGPT (Codex) на Windows без использования Microsoft Store Fabien159 28.10.2026 Здравствуйте всем читающим! Опишу процесс установки ChatGPT (Codex) на Windows, если по каким-то причинам у вас не получается устанавить его через Microsoft Store. И так: 1. Скачиваем с. . .

@marymap 2 / 2 / 1 Регистрация: 28.11.2016 Сообщений: 85

	Найти минимальное число ходов, которые нужны шахматному коню 26.09.2017, 22:30. Показов 7564. Ответов 25 Метки нет (Все метки) Даны обозначения двух полей шахматной доски (например, A5 и C2). Найти минимальное число ходов, которые нужны шахматному коню для перехода с первого поля на второе. реализовать нужно через очередь,но я пока не могу представить,как это делать.Подскажите, пожалуйста, как она должна работать 0

@Старый воин 93 / 92 / 21 Регистрация: 16.08.2017 Сообщений: 188 Записей в блоге: 1
	05.10.2017, 00:20
	AlexVRud, красиво! 0

Найти минимальное число ходов, которые нужны шахматному коню

Решение