Задача. Указать маршрут коня. Начинающегося на одном заданном поле шахматной доски и оканчивающемся на другом. Никакое поле не должно встречаться в маршруте дважды.
Пример
| Входные данные | Выходные данные |
| a1
b1 |
a1 b3 d2 b1 |
| a1 h8 |
a1 c2 e3 g2 h4 g6 h8 |
Решение
|
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 |
#include <iostream> #include <math.h> using namespace std; struct coord { int x,y; }; const int n=8; int main() { int chessboard[n][n]; bool k; string s0,s1; int step=0; coord start, finish; cin>>s0>>s1; start.x=(int)s0[0]-97; start.y=s0[1]-49; finish.x=(int)s1[0]-97; finish.y=s1[1]-49; for(int i=0;i<n;i++) for(int j=0;j<n;j++) chessboard[i][j]=-1; chessboard[start.x][start.y]=0; k=true; while(chessboard[finish.x][finish.y]==-1) { k=false; for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(chessboard[i][j]==step) { for(int a=fmax(0,i-2);a<=fmin(n-1,i+2);a++) for(int b=fmax(0,j-2);b<=fmin(n-1,j+2);b++) if((chessboard[a][b]==-1)&&(((abs(i-a)==2)&&(abs(j-b)==1))||((abs(i-a)==1)&&(abs(j-b)==2)))) { chessboard[a][b]=step+1; k=true; } } if(!k) chessboard[finish.x][finish.y]=0; else step++; } if (chessboard[finish.x][finish.y]==0) cout<<"start=finish"<<endl; else { coord path[8]; path[0].x=finish.x; path[0].y=finish.y; for(int i=0;i<step;i++) { int x=path[i].x; int y=path[i].y; for(int a=fmax(0,x-2);a<=fmin(n-1,x+2);a++) for(int b=fmax(0,y-2);b<=fmin(n-1,y+2);b++) if((chessboard[a][b]==chessboard[x][y]-1)&&(((abs(x-a)==2)&&(abs(y-b)==1))||((abs(x-a)==1)&&(abs(y-b)==2)))) { path[i+1].x=a; path[i+1].y=b; } } for(int i=step;i>=0;i--) cout<<(char)(path[i].x+97)<<path[i].y+1<<endl; } return 0; } |
Читаем входные данные. Преобразуем их в координаты начального и финального поля на шахматной доске. Массив chessboard сначала заполняем -1 (не пройденные поля), затем значение в поле с начальными координатами присваиваем 0. Затем будем отмечать все доступные ходы коня до тех пор пока не изменится значение в финальном поле. Затем, если у нас не совпали начальное и финальное поле будем восстанавливать путь коня. Создаем массив в котором и будет путь коня. Первое значение которое мы заносим в массив будет наше финальное поле. Затем с этого поля будем рассматривать все возможные ходы которые пройдут по уже помеченным клеткам. Если в финальное поле можно было попасть несколькими путями одинаковой длины то нам не имеет значение каким из них возвращаться в начальное поле. Затем выводим массив пути в обратном порядке.
e-olimp.com тоже есть эта задача — 3740. Снова про коней. И не только там. Задача очень популярна.
Скажите, решение принадлежит Вам?