問題

E – Bishop 2

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

記録

• 2022/6/19 バーチャル参加　解法わからず。

解法

• あとで書く。
• 反省記録はこちら(未作成）

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
const int INF = 1001001001;

int main() {
  int N;
  cin >> N;

  vector<string> maze(N);
  vector<vector<vector<int>>> dist(N, vector<vector<int>>(N, vector<int>(4, INF)));
  vector<vector<vector<bool>>> flg(N, vector<vector<bool>>(N, vector<bool>(4, false)));
  deque<pair<P, int>> que;

  int sy, sx;
  cin >> sy >> sx;
  sy--;
  sx--;
  int gy, gx;
  cin >> gy >> gx;
  gy--;
  gx--;

  for(int i = 0; i < N; ++i) {
    cin >> maze[i];
  }

  vector<int> dy = {-1, -1, 1, 1};
  vector<int> dx = {-1, 1, -1, 1};

  rep(i, 4) {
    int cx = sx + dx[i];
    int cy = sy + dy[i];
    if(cx < 0 || N <= cx || cy < 0 || N <= cy) {
      continue;
    }
    if(maze[cy][cx] == '#') {
      continue;
    }
    dist[cy][cx][i] = 1;
    que.push_back(make_pair(make_pair(cy, cx), i));
  }

  while(!que.empty()) {
    int h = que.front().first.first;
    int w = que.front().first.second;
    int a = que.front().second;
    que.pop_front();

    if(w == gx && h == gy) {
      cout << dist[gy][gx][a] << endl;
      return 0;
    }

    int cy = h;
    int cx = w;
    if (flg[cy][cx][a]) {
      continue;
    }
    flg[cy][cx][a] = true;
    int cd = dist[cy][cx][a];

    for(int i = 0; i < 4; ++i) {
      int nh = h + dy[i];
      int nw = w + dx[i];
      if(nh < 0 || N <= nh || nw < 0 || N <= nw) {
        continue;
      }
      if(maze[nh][nw] == '#') {
        continue;
      }

      int nd = cd;
      if (i != a) {
        nd++;
      }
      if (nd < dist[nh][nw][i]) {
        dist[nh][nw][i] = nd;
        if (i == a) {
          que.push_front(make_pair(make_pair(nh, nw), i));
        } else {
          que.push_back(make_pair(make_pair(nh, nw), i));
        }
      }
    }
  }

  cout << -1 << endl;

  return 0;
}