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