結果
| 問題 |
No.1572 XI
|
| コンテスト | |
| ユーザー |
 stoq
|
| 提出日時 | 2021-06-27 13:33:41 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,536 ms / 2,000 ms |
| コード長 | 6,210 bytes |
| コンパイル時間 | 2,572 ms |
| コンパイル使用メモリ | 212,956 KB |
| 最終ジャッジ日時 | 2025-01-22 14:03:33 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 45 |
ソースコード
#define MOD_TYPE 2
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
#if 1
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
#if 0
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template <typename T>
using extset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif
#if 0
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
using Int = boost::multiprecision::cpp_int;
using lld = boost::multiprecision::cpp_dec_float_100;
#endif
using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
template <typename T>
using smaller_queue = priority_queue<T, vector<T>, greater<T>>;
constexpr ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
constexpr int INF = (int)1e9 + 10;
constexpr ll LINF = (ll)4e18;
constexpr ld PI = acos(-1.0);
constexpr ld EPS = 1e-7;
constexpr int Dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0};
constexpr int Dy[] = {1, -1, 0, 0, -1, -1, 1, 1, 0};
#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define REPI(i, m, n) for (int i = m; i < (int)(n); ++i)
#define repi(i, n) REPI(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << "\n"
#define Yes(n) cout << ((n) ? "Yes" : "No") << "\n"
#define possible(n) cout << ((n) ? "possible" : "impossible") << "\n"
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << "\n"
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << "\n";
struct io_init
{
io_init()
{
cin.tie(0);
ios::sync_with_stdio(false);
cout << setprecision(30) << setiosflags(ios::fixed);
};
} io_init;
template <typename T>
inline bool chmin(T &a, T b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
template <typename T>
inline bool chmax(T &a, T b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
inline ll CEIL(ll a, ll b)
{
return (a + b - 1) / b;
}
template <typename A, size_t N, typename T>
inline void Fill(A (&array)[N], const T &val)
{
fill((T *)array, (T *)(array + N), val);
}
template <typename T, typename U>
constexpr istream &operator>>(istream &is, pair<T, U> &p) noexcept
{
is >> p.first >> p.second;
return is;
}
template <typename T, typename U>
constexpr ostream &operator<<(ostream &os, pair<T, U> &p) noexcept
{
os << p.first << " " << p.second;
return os;
}
#pragma endregion
// --------------------------------------
template <typename T>
struct dijkstra
{
int V;
T INF_d;
struct edge
{
int to;
T cost;
};
vector<vector<edge>> E;
vector<T> d;
using pt = pair<T, int>;
dijkstra(int V_) : V(V_)
{
E.resize(V);
d.resize(V);
if (is_same<int, T>::value)
INF_d = 2e9;
else
INF_d = 8e18;
}
void add_edge(int a, int b, T c = 1, bool directed = true)
{
E[a].emplace_back(edge{b, c});
if (!directed)
E[b].emplace_back(edge{a, c});
}
void calc(int s)
{
priority_queue<pt, vector<pt>, greater<pt>> que;
fill(d.begin(), d.end(), INF_d);
que.emplace(T(0), s);
d[s] = 0;
while (!que.empty())
{
pt p = que.top();
que.pop();
int v = p.second;
if (d[v] < p.first)
continue;
for (auto &&e : E[v])
{
if (d[e.to] > d[v] + e.cost)
{
d[e.to] = d[v] + e.cost;
que.emplace(d[e.to], e.to);
}
}
}
}
};
template <typename T>
inline void roll(int i, int j, int k, int l, T *a)
{
T t = a[i];
a[i] = a[j];
a[j] = a[k];
a[k] = a[l];
a[l] = t;
}
enum
{
U,
F,
R,
L,
B,
D
};
/*
.0..
3124
.5..
.U..
LFRB
.D..
.N.
W.E
.S.
*/
struct Dice
{
int a[6];
int &operator[](int i) { return a[i]; }
Dice() { fill(a, a + 6, -1); }
void roll_x() { roll(U, F, D, B, a); } // N
void roll_y() { roll(U, R, D, L, a); } // W
void roll_z() { roll(B, R, F, L, a); } // counter-clockwise
void move(char c)
{
assert(c == 'E' or c == 'W' or c == 'N' or c == 'S');
if (c == 'E')
rep(i, 3) roll_y();
if (c == 'W')
roll_y();
if (c == 'N')
roll_x();
if (c == 'S')
rep(i, 3) roll_x();
}
int getR(int u, int f) // 右面の index
{
int res = -1;
rep(i, 6)
{
rep(j, 4)
{
if (a[U] == u and a[F] == f)
res = a[R];
roll_z();
}
i & 1 ? roll_x() : roll_y();
}
return res;
}
};
int Dtoi(Dice &d)
{
rep(i, 6)
{
if (d[i] == 1)
return i;
}
assert(0);
}
Dice itoD(int k)
{
Dice dice;
rep(i, 6) dice[i] = i == k;
return dice;
}
bool Same(Dice &d1, Dice &d2)
{
bool res = false;
rep(i, 6)
{
rep(j, 4)
{
bool s = true;
rep(k, 6)
{
if (d1.a[k] != d2.a[k])
{
s = false;
break;
}
}
res |= s;
d2.roll_z();
}
i % 2 == 0 ? d2.roll_y() : d2.roll_x();
}
return res;
}
void solve()
{
int h, w;
cin >> h >> w;
int si, sj, gi, gj;
cin >> si >> sj >> gi >> gj;
si--, sj--, gi--, gj--;
string s[1000];
rep(i, h) cin >> s[i];
dijkstra<int> ds(h * w * 6);
auto f = [&](int i, int j, int k)
{ return (i * w + j) * 6 + k; };
rep(i, h) rep(j, w) rep(k, 6)
{
if (s[i][j] == '#')
continue;
Dice d = itoD(k);
rep(di, 4)
{
int ii = i + Dx[di];
int jj = j + Dy[di];
if (ii < 0 or ii >= h or jj < 0 or jj >= w or s[ii][jj] == '#')
continue;
Dice nxt = d;
if (di == 0)
nxt.move('E');
else if (di == 1)
nxt.move('W');
else if (di == 2)
nxt.move('N');
else if (di == 3)
nxt.move('S');
ds.add_edge(f(i, j, k), f(ii, jj, Dtoi(nxt)));
}
}
ds.calc(f(si, sj, 0));
int d = ds.d[f(gi, gj, 0)];
if (d == ds.INF_d)
cout << -1 << "\n";
else
cout << d << "\n";
}
int main()
{
solve();
}