We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Search
  4. Red Knight's Shortest Path
  5. Discussions

Red Knight's Shortest Path

  • xdavidliu
     + 3 comments

    optimal C++ solution that passes all test cases and is O(1) whenever "Impossible" and otherwise O(max(|i_start-i_end|, |j_start-j_end|)), which is at most O(n). The idea is that all reachable positions form a hexagonal lattice, so we can check in O(1) time whether it's possible based on the parities of iend-istart and jend-jstart. If it is possible, then we can split into two general cases: case 1 is when abs(ie-is) <= 2 abs(je-js) for which case it's trivial; just move diagonally in one direction and horizontally to make up the distance (or those two in the opposite order, depending on the priorities). Case 2 is when abs(ie-is) > 2 abs(je-js), for which case it's slightly trickier, but always consists of moving diagonally in one direction then diagonally in another. In case 2 we need to watch out for going out of bounds and zigzag along the border to prevent that from happening, but otherwise it's not too difficult.

    #include <iostream>

int abs(int i){ return i<0? -i:i; }

bool both_hex(int di, int dj){
  if(di&1) return false;
  else if(di%4==0) return !(dj&1);
  else return dj&1;
}

void case1(int di, int dj){
  std::cout << abs(di)/2+(abs(dj)-abs(di)/2)/2 << '\n';
  if(di<=0 && dj>0){
    while(di){
      di+=2;
      --dj;
      std::cout << "UR ";
    }
    while(dj){
      dj-=2;
      std::cout << "R ";
    }
  }else if(di<=0 && dj<0){
    while(di){
      di+=2;
      ++dj;
      std::cout << "UL ";
    }
    while(dj){
      dj+=2;
      std::cout << "L ";
    }
  }else if(di>0 && dj>0){
    while(abs(di)!=2*abs(dj)){
      dj-=2;
      std::cout << "R ";
    }
    while(di){
      di-=2;
      --dj;
      std::cout << "LR ";
    }
  }else{
    while(di){
      di-=2;
      ++dj;
      std::cout << "LL ";
    }
    while(dj){
      dj+=2;
      std::cout << "L ";
    }
  }
}

void case2(int n, int is, int js, int ie, int je){
  std::cout << abs(ie-is)/2 << '\n';
  while(ie<is){
    if(js==0 || abs(ie-is)==2*abs(je-js)){
      is-=2;
      ++js;
      std::cout << "UR ";
    }else{
      is-=2;
      --js;
      std::cout << "UL ";
    }
  }
  while(ie>is){
    if(js==n-1 || abs(ie-is)==2*abs(je-js)){
      is+=2;
      --js;
      std::cout << "LL ";
    }else{
      is+=2;
      ++js;
      std::cout << "LR ";
    }
  }
}

void knight(int n, int is, int js, int ie, int je){
  if(abs(ie-is)<=2*abs(je-js)){
    case1(ie-is, je-js);
  }else case2(n, is, js, ie, je);
}

void solve(){
  int n=0, is=0, js=0, ie=0, je=0;
  std::cin >> n >> is >> js >> ie >> je;
  if(both_hex(abs(is-ie),abs(js-je))) knight(n,is,js,ie,je);
  else std::cout << "Impossible";
}

int main(){
  solve();
}