TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

 
 

Bishop 2

問題

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

記録

解法

コード例

#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;
}