AOJ2425 全探索お姉さんの休日

問題ページ
A Holiday of Miss Brute Force | Aizu Online Judge

考えたこと

• 六角形のグリッド上を探索する
• 拡張dijkstraの要領で頂点に時間を増やせばいい気持ちになる
• 時間の上限ないしそのままつけるのは無理
• 時間が影響するのはabs(x*y*t)%6の指示される方向を計算する部分だけ
• 時間はmod 6で持っていても問題なさそう
• d[y][x][t] = (座標y,xに時間tでいるときの最小の指示を無視する回数) として拡張dijkstraをする
• 六角形のグリッドでは位置によってdx,dyが変化するのに注意しつつ実装すると通る

ソースコード

#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }

int dx[] = {0, 1, 1, 0, -1, -1}, dy1[] = {1, 0, -1, -1, -1, 0}, dy2[] = {1, 1, 0, -1, 0, 1};

// d[y][x][t%6] = (ここにたどり着く最小の無視した回数)
int d[250][250][6];
int board[250][250];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int sx, sy, gx, gy;
  cin >> sx >> sy >> gx >> gy;
  int n;
  cin >> n;
  REP(i, n) {
    int x, y;
    cin >> x >> y;
    board[y+100][x+100] = 1;
  }
  int lx, ly;
  cin >> lx >> ly;

  REP(i, 250) REP(j, 250) REP(k, 6) d[i][j][k] = LLINF;
  d[100+sy][100+sx][0] = 0;
  priority_queue<VI, VVI, greater<VI>> que;
  que.push({d[100+sy][100+sx][0], 100+sy, 100+sx, 0});

  while(que.size()) {
    VI v = que.top(); que.pop();
    // cout << v << endl;
    int x = v[2], y = v[1], t = v[3];
    REP(i, 6) {
      int nx = x + dx[i], ny = y + (x%2==0?dy1:dy2)[i];
      if(100-lx <= nx && nx <= 100+lx && 100-ly <= ny && ny <= 100+ly && board[ny][nx]==0) {
        int tmp = abs((x-100)*(y-100)*t)%6 != i;
        // cout << i << " " << nx << " " << ny << " " << tmp << endl;
        if(d[ny][nx][(t+1)%6] > d[y][x][t] + tmp) {
          d[ny][nx][(t+1)%6] = d[y][x][t] + tmp;
          que.push({d[ny][nx][(t+1)%6], ny, nx, (t+1)%6});
        }
      }
    }
    if(d[y][x][(t+1)%6] > d[y][x][t] + 1) {
      d[y][x][(t+1)%6] = d[y][x][t] + 1;
      que.push({d[y][x][(t+1)%6], y, x, (t+1)%6});
    }
  }

  int ans = LLINF;
  REP(i, 6) {
    chmin(ans, d[100+gy][100+gx][i]);
    // cout << d[100+gy][100+gx][i] << endl;
  }
  if(ans==LLINF) cout << -1 << endl;
  else cout << ans << endl;

  return 0;
}