Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Shato
2 / 2 / 0
Регистрация: 16.03.2011
Сообщений: 82
15.04.2011, 14:25     Король шахматной доски #1
Король шахматной доски размером 8х8 находится на коне в одной из клеток своего королевства. Он очень озабочен тем, что некоторые клетки его королевства стали непригодными для путешествия верхом. Поэтому он хочет как можно быстрее добраться в свой замок (наш король всегда путешествует на коне).
Вам предстоит выяснить для него [оптимальный] маршрут или выяснить, что такого не существует.

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

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

Пример

Ввод
A1
A2
B4B3

Вывод
A1C2E1D3C1A2
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
15.04.2011, 16:09     Король шахматной доски #2
Можно решить через граф + алгоритм дейкстры.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.04.2011, 16:41     Король шахматной доски #3
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
2 / 2 / 0
Регистрация: 16.03.2011
Сообщений: 82
16.04.2011, 12:50  [ТС]     Король шахматной доски #4
Посоветуйте пожалуйста хорошую и нужную литературу по графам. То, что пригодиться в c++

Добавлено через 18 часов 51 минуту
В интернете не хочу искать сам. Посоветуйте кто чем пользуется
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
16.04.2011, 19:29     Король шахматной доски #5
Посоветуйте кто чем пользуется
http://www.google.com/ хорошо ищет
Yandex
Объявления
16.04.2011, 19:29     Король шахматной доски
Ответ Создать тему
Опции темы

Текущее время: 18:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru