kananasgarli90

Knight Moves

Sep 18th, 2020
895
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int color[9][9], dis[9][9], a1, a2;
  4. char c1, c2;
  5. void bfs(int x, int y){
  6.     queue<pair<int ,int> > q;
  7.     q.push(make_pair(x, y));
  8.     while(q.size() != 0){
  9.         pair<int, int> p = q.front();
  10.         int i = p.first;
  11.         int j = p.second;
  12.         if(i - 2 > 0 && j - 1 > 0 && color[i-2][j-1] == 0){
  13.             q.push(make_pair(i-2, j-1));
  14.             dis[i-2][j-1] = dis[i][j] + 1;
  15.         }
  16.         if(i - 2 > 0 && j + 1 <= 8 && color[i-2][j+1] == 0){
  17.             q.push(make_pair(i-2, j+1));
  18.             dis[i-2][j+1] = dis[i][j] + 1;
  19.         }
  20.         if(i - 1 > 0 && j + 2 <= 8 && color[i-1][j+2] == 0){
  21.             q.push(make_pair(i-1, j+2));
  22.             dis[i-1][j+2] = dis[i][j] + 1;
  23.         }
  24.         if(i + 1 <= 8 && j + 2 <= 8 && color[i+1][j+2] == 0){
  25.             q.push(make_pair(i+1, j+2));
  26.             dis[i+1][j+2] = dis[i][j] + 1;
  27.         }
  28.         if(i + 2 <= 8 && j + 1 <= 8 && color[i+2][j+1] == 0){
  29.             q.push(make_pair(i+2, j+1));
  30.             dis[i+2][j+1] = dis[i][j] + 1;
  31.         }
  32.         if(i + 2 <= 8 && j - 1 > 0 && color[i+2][j-1] == 0){
  33.             q.push(make_pair(i+2, j-1));
  34.             dis[i+2][j-1] = dis[i][j] + 1;
  35.         }
  36.         if(i + 1 <= 8 && j - 2 > 0 && color[i+1][j-2] == 0){
  37.             q.push(make_pair(i+1, j-2));
  38.             dis[i+1][j-2] = dis[i][j] + 1;
  39.         }
  40.         if(i - 1 > 0 && j - 2 > 0 && color[i-1][j-2] == 0){
  41.             q.push(make_pair(i-1, j-2));
  42.             dis[i-1][j-2] = dis[i][j] + 1;
  43.         }
  44.  
  45.         q.pop();
  46.         color[i][j] = 1;
  47.     }
  48. }
  49.  
  50. void initialize(){
  51.     for(int i = 1; i <= 8; i++){
  52.         for(int j = 1; j <= 8; j++){
  53.             color[i][j] = dis[i][j] = 0;
  54.         }
  55.     }
  56. }
  57.  
  58. int main()
  59. {
  60.     while(cin>>c1>>a1>>c2>>a2){
  61.         bfs(a1, c1-96);
  62.         cout<<"To get from "<<c1<<a1<<" to "<<c2<<a2<<" takes "<<dis[a2][c2-96]<<" knight moves."<<endl;
  63.         initialize();
  64.     }
  65. }
  66.  
RAW Paste Data