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
|
#include <iostream>
#include <vector>
#include <iomanip>
typedef std::vector<std::vector<int>> field_t;
struct point_t { int row, col; };
int n;
int row, col;
field_t field;
std::vector<point_t>
neighbors(int row, int col)
{
std::vector<point_t> v;
std::vector<point_t> possible = {
{ row - 2, col - 1 },
{ row - 1, col - 2 },
{ row + 1, col - 2 },
{ row + 2, col - 1 },
{ row - 2, col + 1 },
{ row - 1, col + 2 },
{ row + 1, col + 2 },
{ row + 2, col + 1 },
};
for (point_t p : possible)
{
if (p.row >= 0 && p.row < n &&
p.col >= 0 && p.col < n)
{
v.push_back(p);
}
}
return v;
}
bool
tour(int row, int col, int step, field_t field, field_t &result)
{
for (point_t p : neighbors(row, col))
{
if (field[p.row][p.col] != 0) continue;
field[p.row][p.col] = step;
if (step == n * n)
{
result = field;
return true;
}
if (tour(p.row, p.col, step + 1, field, result))
{
return true;
}
field[p.row][p.col] = 0;
}
return false;
}
int
main()
{
std::cout << "Размер поля (n): ";
std::cin >> n;
std::cout << "Положение коня (ряд, колонка): ";
std::cin >> row >> col;
row--;
col--;
field = std::vector(n, std::vector<int>(n));
field[row][col] = 1;
field_t result(n, std::vector<int>(n));
bool found = tour(row, col, 2, field, result);
int width = 0;
{
int q = n * n;
while (q > 0)
{
width++;
q /= 10;
}
}
if (found)
{
std::cout << "Обход конём найден:" << std::endl;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
std::cout << std::setw(width + 1) << result[i][j];
if (j < n - 1) std::cout << ' ';
}
if (i < n - 1) std::cout << '\n';
}
std::cout << std::endl;
}
else
{
std::cout << "Обход конём не найден" << std::endl;
}
}
|
