No.240 ナイト散歩 - 名もなき未知

久々に更新しておこうと思う．

問題

回答

タグにあるとおりで，幅優先探索していく．
本当は，要素数が3つの配列をqueueに突っ込みたかったが，方法がわからず，断念．

pair< <pair<int, int>, int>

のような方法で突っ込んでいる人がいたので，それを参考にしてみました…．
しかし，今後queueに配列を突っ込みたい時に困りますね… どうしたらいいんだろう．
（vectorとかは突っ込めるのかなあ^^；）

queueを使うにあたり，少し調べたもののリンク
C++ キュー
 std::queue - C++入門

もう少しマスが多くなったら，すでに行ったマスをマークするみたいな方法で計算量減らせるんですかね…．

C++で幅優先探索を書いたのは初めてだけど，algorithm的にはすぐかけるものの，言語仕様に苦戦した．（絶対pythonならささっとリストにリストをぶち込む） C++にもっとなれる必要がある．

int mx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int my[] = {-1, 1, -2, 2, -2, 2, -1, 1};

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(16);

  int X, Y;
  cin >> X >> Y;

  queue< pair< pair<int, int>, int> > que;
  pair<int, int> p = mp(0, 0);
  que.push(mp(p, 0));
  while(!que.empty()) {
      pair<int, int> current = que.front().first;
      int count = que.front().second;
      que.pop();

      if(count >= 3) continue;
      REP(i, 8) {
          int nx = current.first + mx[i];
          int ny = current.second + my[i];
          if(nx == X && ny == Y) {
              cout << "YES" << endl;
              return 0;
          }

          if(count <= 2) {
              pair<int, int> nextpoint = mp(nx, ny);
              que.push(mp(nextpoint, count + 1));
          }
      }
  }

  cout << "NO" << endl;
  return 0;
}