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

@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/ хорошо ищет

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

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

	Король шахматной доски 15.04.2011, 14:25. Показов 2377. Ответов 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