Король шахматной доски

@Shato · Регистрация: 16.03.2011

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

Король шахматной доски размером 8х8 находится на коне в одной из клеток своего королевства. Он очень озабочен тем, что некоторые клетки его королевства стали непригодными для путешествия верхом. Поэтому он хочет как можно быстрее добраться в свой замок (наш король всегда путешествует на коне).
Вам предстоит выяснить для него [оптимальный] маршрут или выяснить, что такого не существует.

Входные данные
Во входном файле в первой строке содержится индекс клетки, в которой находится король (доска прономерована от 'A' до 'H' слева направо и от 1 до 8 снизу вверх). Во второй строке находится индекс клетки, в которой находится замок короля. В третьей строке без пробелов перечислены клетки, по которым нельзя проехать верхом.

Выходные данные
В выходной файл необходимо вывести маршрут короля без пробелов в том же формате или число 0, если маршрута не существует.

Пример

Ввод
A1
A2
B4B3

Вывод
A1C2E1D3C1A2

@Overmind024 · 15.04.2011, 16:09

Можно решить через граф + алгоритм дейкстры.

valeriikozlov · 15.04.2011, 16:41

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
#include <stdio.h>
#include <string.h>
int main () 
{
      freopen("input.txt","r",stdin);
      freopen("output.txt","w",stdout);
      int mas[8][8], Q[64][2], i_st=0, i_end=1, i, j, y, st1, st2;
      for(i=0; i<8; i++)
          for(j=0; j<8; j++)
              mas[i][j]=0;
      char str[129];
      scanf("%s\n", &str);
      mas[(int)(str[0]-'A')][(int)(str[1]-'1')]=1;
      st1=Q[0][0]=(int)(str[0]-'A'); st2=Q[0][1]=(int)(str[1]-'1');
      scanf("%s\n", &str);
      i=(int)(str[0]-'A'); j=(int)(str[1]-'1');
      scanf("%s", &str);
      for(y=0; y<(int)strlen(str); y+=2)
      {
          mas[(int)(str[y]-'A')][(int)(str[y+1]-'1')]=-1;
      }
      while(i_st<i_end && mas[i][j]==0)
      {
          if(Q[i_st][0]>1 && Q[i_st][1]>0 && mas[Q[i_st][0]-2][Q[i_st][1]-1]==0)
          {
              Q[i_end][0]=Q[i_st][0]-2; Q[i_end++][1]=Q[i_st][1]-1; mas[Q[i_st][0]-2][Q[i_st][1]-1]=mas[Q[i_st][0]][Q[i_st][1]]+1;
          }
          if(Q[i_st][0]>1 && Q[i_st][1]<7 && mas[Q[i_st][0]-2][Q[i_st][1]+1]==0)
          {
              Q[i_end][0]=Q[i_st][0]-2; Q[i_end++][1]=Q[i_st][1]+1; mas[Q[i_st][0]-2][Q[i_st][1]+1]=mas[Q[i_st][0]][Q[i_st][1]]+1;
          }
          if(Q[i_st][0]>0 && Q[i_st][1]>1 && mas[Q[i_st][0]-1][Q[i_st][1]-2]==0)
          {
              Q[i_end][0]=Q[i_st][0]-1; Q[i_end++][1]=Q[i_st][1]-2; mas[Q[i_st][0]-1][Q[i_st][1]-2]=mas[Q[i_st][0]][Q[i_st][1]]+1;
          }
          if(Q[i_st][0]>0 && Q[i_st][1]<6 && mas[Q[i_st][0]-1][Q[i_st][1]+2]==0)
          {
              Q[i_end][0]=Q[i_st][0]-1; Q[i_end++][1]=Q[i_st][1]+2; mas[Q[i_st][0]-1][Q[i_st][1]+2]=mas[Q[i_st][0]][Q[i_st][1]]+1;
          }
          if(Q[i_st][0]<6 && Q[i_st][1]>0 && mas[Q[i_st][0]+2][Q[i_st][1]-1]==0)
          {
              Q[i_end][0]=Q[i_st][0]+2; Q[i_end++][1]=Q[i_st][1]-1;mas[Q[i_st][0]+2][Q[i_st][1]-1]=mas[Q[i_st][0]][Q[i_st][1]]+1;
          }
          if(Q[i_st][0]<6 && Q[i_st][1]<7 && mas[Q[i_st][0]+2][Q[i_st][1]+1]==0)
          {
              Q[i_end][0]=Q[i_st][0]+2; Q[i_end++][1]=Q[i_st][1]+1; mas[Q[i_st][0]+2][Q[i_st][1]+1]=mas[Q[i_st][0]][Q[i_st][1]]+1;
          }
          if(Q[i_st][0]<7 && Q[i_st][1]>1 && mas[Q[i_st][0]+1][Q[i_st][1]-2]==0)
          {
              Q[i_end][0]=Q[i_st][0]+1; Q[i_end++][1]=Q[i_st][1]-2; mas[Q[i_st][0]+1][Q[i_st][1]-2]=mas[Q[i_st][0]][Q[i_st][1]]+1;
          }
          if(Q[i_st][0]<7 && Q[i_st][1]<6 && mas[Q[i_st][0]+1][Q[i_st][1]+2]==0)
          {
              Q[i_end][0]=Q[i_st][0]+1; Q[i_end++][1]=Q[i_st][1]+2; mas[Q[i_st][0]+1][Q[i_st][1]+2]=mas[Q[i_st][0]][Q[i_st][1]]+1;
          }
          i_st++;
      }
      if(mas[i][j]==0)
          printf("0\n");
      else
      {
          Q[0][0]=i; Q[0][1]=j;
          i=0;
          while(mas[Q[i][0]][Q[i][1]]!=1)
          {
              if(Q[i][0]>1 && Q[i][1]>0 && mas[Q[i][0]][Q[i][1]]==mas[Q[i][0]-2][Q[i][1]-1]+1)
              {
                  Q[i+1][0]=Q[i][0]-2; Q[i+1][1]=Q[i][1]-1; i++;
              }
              else
                  if(Q[i][0]>1 && Q[i][1]<7 && mas[Q[i][0]][Q[i][1]]==mas[Q[i][0]-2][Q[i][1]+1]+1)
                  {
                      Q[i+1][0]=Q[i][0]-2; Q[i+1][1]=Q[i][1]+1; i++;
                  }
                  else
                      if(Q[i][0]>0 && Q[i][1]>1 && mas[Q[i][0]][Q[i][1]]==mas[Q[i][0]-1][Q[i][1]-2]+1)
                      {
                          Q[i+1][0]=Q[i][0]-1; Q[i+1][1]=Q[i][1]-2; i++;
                      }
                      else
                          if(Q[i][0]>0 && Q[i][1]<6 && mas[Q[i][0]][Q[i][1]]==mas[Q[i][0]-1][Q[i][1]+2]+1)
                          {
                              Q[i+1][0]=Q[i][0]-1; Q[i+1][1]=Q[i][1]+2; i++;
                          }
                          else
                              if(Q[i][0]<6 && Q[i][1]>0 && mas[Q[i][0]][Q[i][1]]==mas[Q[i][0]+2][Q[i][1]-1]+1)
                              {
                                  Q[i+1][0]=Q[i][0]+2; Q[i+1][1]=Q[i][1]-1; i++;
                              }
                              else
                                  if(Q[i][0]<6 && Q[i][1]<7 && mas[Q[i][0]][Q[i][1]]==mas[Q[i][0]+2][Q[i][1]+1]+1)
                                  {
                                      Q[i+1][0]=Q[i][0]+2; Q[i+1][1]=Q[i][1]+1; i++;
                                  }
                                  else
                                      if(Q[i][0]<7 && Q[i][1]>1 && mas[Q[i][0]][Q[i][1]]==mas[Q[i][0]+1][Q[i][1]-2]+1)
                                      {
                                          Q[i+1][0]=Q[i][0]+1; Q[i+1][1]=Q[i][1]-2; i++;
                                      }
                                      else
                                          if(Q[i][0]<7 && Q[i][1]<6 && mas[Q[i][0]][Q[i][1]]==mas[Q[i][0]+1][Q[i][1]+2]+1)
                                          {
                                              Q[i+1][0]=Q[i][0]+1; Q[i+1][1]=Q[i][1]+2; i++;
                                          }
          }
          printf("%c%c", (char)(st1+'A'), (char)(st2+'1'));
          for(j=i-1; j>=0; j--)
              printf("%c%c", (char)(Q[j][0]+'A'), (char)(Q[j][1]+'1')); 
      }
    return 0; 
}

@Shato · 16.04.2011, 12:50 **[ТС]**

Посоветуйте пожалуйста хорошую и нужную литературу по графам. То, что пригодиться в c++

Добавлено через 18 часов 51 минуту
В интернете не хочу искать сам. Посоветуйте кто чем пользуется

@odip · 16.04.2011, 19:29

Посоветуйте кто чем пользуется

http://www.google.com/ хорошо ищет

Новые блоги и статьи Все статьи Все блоги /
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .

@Shato 2 / 2 / 1 Регистрация: 16.03.2011 Сообщений: 82

	Король шахматной доски 15.04.2011, 14:25. Показов 2400. Ответов 4 Метки нет (Все метки) Король шахматной доски размером 8х8 находится на коне в одной из клеток своего королевства. Он очень озабочен тем, что некоторые клетки его королевства стали непригодными для путешествия верхом. Поэтому он хочет как можно быстрее добраться в свой замок (наш король всегда путешествует на коне). Вам предстоит выяснить для него [оптимальный] маршрут или выяснить, что такого не существует. Входные данные Во входном файле в первой строке содержится индекс клетки, в которой находится король (доска прономерована от 'A' до 'H' слева направо и от 1 до 8 снизу вверх). Во второй строке находится индекс клетки, в которой находится замок короля. В третьей строке без пробелов перечислены клетки, по которым нельзя проехать верхом. Выходные данные В выходной файл необходимо вывести маршрут короля без пробелов в том же формате или число 0, если маршрута не существует. Пример Ввод A1 A2 B4B3 Вывод A1C2E1D3C1A2 0

@Overmind024 101 / 101 / 27 Регистрация: 10.09.2010 Сообщений: 267
	15.04.2011, 16:09
	Можно решить через граф + алгоритм дейкстры. 0

@Shato 2 / 2 / 1 Регистрация: 16.03.2011 Сообщений: 82
	16.04.2011, 12:50 [ТС]
	Посоветуйте пожалуйста хорошую и нужную литературу по графам. То, что пригодиться в c++ Добавлено через 18 часов 51 минуту В интернете не хочу искать сам. Посоветуйте кто чем пользуется 0