Advertisement
kadeyrov

Untitled

Sep 17th, 2020
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.80 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <string>
  6. #include <vector>
  7.  
  8. using namespace std;
  9.  
  10. const int inf = 1000000;
  11.  
  12. struct Point {
  13.     int x, y;
  14. };
  15.  
  16. int a[500][500];
  17.  
  18. int n;
  19.  
  20. bool cheak(int X, int Y) {
  21.     return ((X < n) && (X >= 0)) && ((Y < n) && (Y >= 0));
  22. }
  23.  
  24. void make_inf() {
  25.     for(int i = 0; i < 500; i++)
  26.         for(int j = 0; j < 500; j++)
  27.             if(i == j) a[i][j] = 0;
  28.             else a[i][j] = inf;
  29. }
  30.  
  31. int main() {
  32.    
  33.     make_inf();
  34.    
  35.     //Point start, finish;
  36.    
  37.     vector < pair<int, int> > points_start, points_finish;
  38.    
  39.     n = 8;
  40.    
  41.     //cout << cheak(-1, 0);
  42.    
  43.     string s1, s2;
  44.     char l1, l2, n1, n2;
  45.    
  46.     while(cin >> s1  >> s2) {
  47.         l1 = s1[0], l2 = s2[0];
  48.         n1 = s1[1], n2 = s2[1];
  49.        
  50.         n1 -= '0';
  51.         n2 -= '0';
  52.  
  53.         n1--, n2--;
  54.        
  55.         l1 -= 'a';
  56.         l2 -= 'a';
  57.         //cout << (int)l1 << ' ' << n1 << ' ' << l2 << ' ' << n2 << endl;
  58.         points_start.push_back(make_pair(l1, n1));
  59.         points_finish.push_back(make_pair(l2, n2));
  60.         //break;
  61.     }
  62.    
  63.     for(int i = 0; i < n; i++) {
  64.         for(int j = 0; j < n; j++) {
  65.             if(cheak(i + 2, j - 1)) a[i * n + j][(i + 2) * n + (j - 1)] = 1;
  66.             if(cheak(i + 2, j + 1)) a[i * n + j][(i + 2) * n + (j + 1)] = 1;
  67.            
  68.             if(cheak(i - 2, j - 1)) a[i * n + j][(i - 2) * n + (j - 1)] = 1;
  69.             if(cheak(i - 2, j + 1)) a[i * n + j][(i - 2) * n + (j + 1)] = 1;
  70.            
  71.             if(cheak(i - 1, j - 2)) a[i * n + j][(i - 1) * n + (j - 2)] = 1;
  72.             if(cheak(i + 1, j - 2)) a[i * n + j][(i + 1) * n + (j - 2)] = 1;
  73.            
  74.             if(cheak(i - 1, j + 2)) a[i * n + j][(i - 1) * n + (j + 2)] = 1;
  75.             if(cheak(i + 1, j + 2)) a[i * n + j][(i + 1) * n + (j + 2)] = 1;
  76.         }
  77.     }
  78.    
  79.    // for(int i = 0; i < n * n; i++) {for(int j = 0; j < n * n; j++)printf("%3d ", a[i][j]);cout << endl;}
  80.    
  81.     for (int k=0; k<n*n; ++k)
  82.         for (int i=0; i<n*n; ++i)
  83.             for (int j=0; j<n*n; ++j)
  84.                 if (a[i][k] < inf && a[k][j] < inf)
  85.                     a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
  86.    
  87.     //if(a[start.x * n + start.y][finish.x * n + start . y] <= n + 2)
  88.    
  89.     for(int i = 0; i < points_start.size(); i++)
  90.     cout << "To get from " << (char)(points_start[i].first+'a') << points_start[i].second + 1 << " to " << (char)(points_finish[i].first + 'a') << points_finish[i].second + 1<< " takes " << a[points_start[i].first * n + points_start[i].second][points_finish[i].first * n + points_finish[i].second] <<" knight moves.\n";
  91.         //cout << a[points_start[i].first * n + points_start[i].second][points_finish[i].first * n + points_finish[i].second] << endl;
  92. }
  93.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement