読者です 読者をやめる 読者になる 読者になる

水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

No.240 ナイト散歩

yukicoder 競技プログラミング C++

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

回答

#55893 No.240 ナイト散歩 - yukicoder

タグにあるとおりで,幅優先探索していく.
本当は,要素数が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;
}