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.
#include <iostream>
using namespace std;
#define N 5
class stack
{
int st[N*N][ 2 ]; //массив хранящий в себе информацию о передвижениях коня
int obr[N*N*N*N][ 4 ]; //массив с записями обращений из main
short top; //счетчик элементов в стеке
public:
stack(): top(- 1 ) {for(int i= 0 ; i<N*N; i++) {st[i][ 0 ]= 0 ; st[i][ 1 ]= 1 ; }}
void push(int var_i, char var_c) { st[++top][ 0 ]=var_i; st[top][ 1 ]=(int)var_c; } //функция добавления элемента в стек
int& pop() { return st[top--][ 0 ];} //функция возвращающая элемент стека
int& out_c() { return st[top][ 1 ];} //функция возвращающая элемент стека
int& out_i() { return st[top][ 0 ];} //функция возвращающая элемент стека
void begin(); //прототип функции ввода начальных координат коня
void step( stack&); //прототип функции хода коня по полю
short& p_top() { return top;} //функция возвращающая номер текущего элемента стека
int end_p (int,char,int,char); //прототип функции проверки границ поля
friend int prov_z (int,int,stack&); //прототип функции проверки занятых точек
};
//////////////////////////////////
void stack::begin () //функция ввода начальных координат коня
{
int v;
char c;
cout<<"Введите координаты коня на поле: ";
cin>>c>>v;
push(v,(char&)c);
};
////////////////////////
int stack::end_p(int p_i,char p_c,int var_i,char var_c) //функция проверки границ поля
{
if ((p_i+var_i>N)||(p_i+var_i< 1 )||(p_c+var_c>char(N+ 96 ))||(p_c+var_c<'a')) return 0 ;
else return 1 ;
}
////////////////
int itop= 0 ;
/////////////////////////////
int prov_z(int p_i,int p_c,stack& si) //проверка занятых клеток
{
for(int i= 0 ; i<si.top; i++)
if (si.st[i][ 0 ]==p_i&&si.st[i][ 1 ]==p_c) return 0 ;
return 1 ;
}
/////////////////////////////////
int poisk_od(int sti1, int sti2,int stj1, int stj2 ,int obr[][ 4 ]) //поиск повторяющихся ходов
{
for (int i= 0 ;i<N*N*N*N;i++)
if ((sti1==obr[i][ 0 ]&&sti2==obr[i][ 1 ]&&stj1==obr[i][ 2 ]&&stj2==obr[i][ 3 ])||(sti1==obr[i][ 2 ]&&sti2==obr[i][ 3 ]&&stj1==obr[i][ 0 ]&&stj2==obr[i][ 1 ])) {obr[i][ 2 ]= 0 ;obr[i][ 3 ]= 0 ; return 0 ; }
return 1 ;
}
//////////////////
void stack::step(stack& si) //функция хода коня
{
if (poisk_od(st[top][ 0 ],st[top][ 1 ],st[top][ 0 ]+ 2 ,st[top][ 1 ]+ 1 ,obr)&&end_p(st[top][ 0 ],st[top][ 1 ], 2 , 1 )&&prov_z(st[top][ 0 ]+ 2 ,st[top][ 1 ]+ 1 ,si)) { obr[itop][ 0 ]=st[top][ 0 ]; obr[itop][ 1 ]=st[top][ 1 ]; obr[itop][ 2 ]=st[top][ 0 ]+ 2 ; obr[itop][ 3 ]=st[top][ 1 ]+ 1 ; itop++; push(st[top][ 0 ]+ 2 ,st[top][ 1 ]+ 1 ); }
else
if (poisk_od(st[top][ 0 ],st[top][ 1 ],st[top][ 0 ]- 2 ,st[top][ 1 ]+ 1 ,obr)&&end_p(st[top][ 0 ],st[top][ 1 ],- 2 , 1 )&&prov_z(st[top][ 0 ]- 2 ,st[top][ 1 ]+ 1 ,si)) { obr[itop][ 0 ]=st[top][ 0 ]; obr[itop][ 1 ]=st[top][ 1 ]; obr[itop][ 2 ]=st[top][ 0 ]- 2 ; obr[itop][ 3 ]=st[top][ 1 ]+ 1 ; itop++;push(st[top][ 0 ]- 2 ,st[top][ 1 ]+ 1 ); }
else
if (poisk_od(st[top][ 0 ],st[top][ 1 ],st[top][ 0 ]+ 2 ,st[top][ 1 ]- 1 ,obr)&&end_p(st[top][ 0 ],st[top][ 1 ], 2 ,- 1 )&&prov_z(st[top][ 0 ]+ 2 ,st[top][ 1 ]- 1 ,si)) { obr[itop][ 0 ]=st[top][ 0 ]; obr[itop][ 1 ]=st[top][ 1 ]; obr[itop][ 2 ]=st[top][ 0 ]+ 2 ; obr[itop][ 3 ]=st[top][ 1 ]- 1 ; itop++;push(st[top][ 0 ]+ 2 ,st[top][ 1 ]- 1 ); }
else
if (poisk_od(st[top][ 0 ],st[top][ 1 ],st[top][ 0 ]- 2 ,st[top][ 1 ]- 1 ,obr)&&end_p(st[top][ 0 ],st[top][ 1 ],- 2 ,- 1 )&&prov_z(st[top][ 0 ]- 2 ,st[top][ 1 ]- 1 ,si)) { obr[itop][ 0 ]=st[top][ 0 ]; obr[itop][ 1 ]=st[top][ 1 ]; obr[itop][ 2 ]=st[top][ 0 ]- 2 ; obr[itop][ 3 ]=st[top][ 1 ]- 1 ; itop++;push(st[top][ 0 ]- 2 ,st[top][ 1 ]- 1 ); }
else
if (poisk_od(st[top][ 0 ],st[top][ 1 ],st[top][ 0 ]+ 1 ,st[top][ 1 ]+ 2 ,obr)&&end_p(st[top][ 0 ],st[top][ 1 ], 1 , 2 )&&prov_z(st[top][ 0 ]+ 1 ,st[top][ 1 ]+ 2 ,si)) { obr[itop][ 0 ]=st[top][ 0 ]; obr[itop][ 1 ]=st[top][ 1 ]; obr[itop][ 2 ]=st[top][ 0 ]+ 1 ; obr[itop][ 3 ]=st[top][ 1 ]+ 2 ;itop++; push(st[top][ 0 ]+ 1 ,st[top][ 1 ]+ 2 ); }
else
if (poisk_od(st[top][ 0 ],st[top][ 1 ],st[top][ 0 ]- 1 ,st[top][ 1 ]+ 2 ,obr)&&end_p(st[top][ 0 ],st[top][ 1 ],- 1 , 2 )&&prov_z(st[top][ 0 ]- 1 ,st[top][ 1 ]+ 2 ,si)) { obr[itop][ 0 ]=st[top][ 0 ]; obr[itop][ 1 ]=st[top][ 1 ]; obr[itop][ 2 ]=st[top][ 0 ]- 1 ; obr[itop][ 3 ]=st[top][ 1 ]+ 2 ;itop++; push(st[top][ 0 ]- 1 ,st[top][ 1 ]+ 2 ); }
else
if (poisk_od(st[top][ 0 ],st[top][ 1 ],st[top][ 0 ]+ 1 ,st[top][ 1 ]- 2 ,obr)&&end_p(st[top][ 0 ],st[top][ 1 ], 1 ,- 2 )&&prov_z(st[top][ 0 ]+ 1 ,st[top][ 1 ]- 2 ,si)) { obr[itop][ 0 ]=st[top][ 0 ]; obr[itop][ 1 ]=st[top][ 1 ]; obr[itop][ 2 ]=st[top][ 0 ]+ 1 ; obr[itop][ 3 ]=st[top][ 1 ]- 2 ; itop++;push(st[top][ 0 ]+ 1 ,st[top][ 1 ]- 2 ); }
else
if (poisk_od(st[top][ 0 ],st[top][ 1 ],st[top][ 0 ]- 1 ,st[top][ 1 ]- 2 ,obr)&&end_p(st[top][ 0 ],st[top][ 1 ],- 1 ,- 2 )&&prov_z(st[top][ 0 ]- 1 ,st[top][ 1 ]- 2 ,si)) { obr[itop][ 0 ]=st[top][ 0 ]; obr[itop][ 1 ]=st[top][ 1 ]; obr[itop][ 2 ]=st[top][ 0 ]- 1 ; obr[itop][ 3 ]=st[top][ 1 ]- 2 ; itop++;push(st[top][ 0 ]- 1 ,st[top][ 1 ]- 2 ); }
else
pop();
}
//////////////////
int main()
{
stack si;
si.begin();
while (si.p_top()!=N*N- 1 ) //цикл до конца заполнения стека
{
if (si.p_top()==- 1 ) {cout<<"Не возможно пройти"<<endl; exit( 1 );}
si.step(si);
// cout<<si.p_top()<<" || "<<si.out_i()<<" "<<(char)si.out_c()<<endl;
}
for (int i= 0 ; i<N*N; i++) //цикл вывода всех элементов стека
cout<<si.pop()<<" "<<(char)si.out_c()<<endl;
return 0 ;
}
