結果
問題 | No.5006 Hidden Maze |
ユーザー |
|
提出日時 | 2022-06-12 16:51:48 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 111 ms / 2,000 ms |
コード長 | 5,454 bytes |
コンパイル時間 | 1,898 ms |
実行使用メモリ | 22,856 KB |
スコア | 0 |
平均クエリ数 | 1000.00 |
最終ジャッジ日時 | 2022-06-12 16:52:06 |
合計ジャッジ時間 | 16,539 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#include <bits/stdc++.h>#include <sys/time.h>using namespace std;void debug() {std::cerr << std::endl;std::cerr << "↑ [line:" << __LINE__ << "]" << std::endl;}template<class Head, class... Tail>void debug(Head&& head, Tail&&... tail) {std::cerr << head << ", ";debug(std::forward<Tail>(tail)...);}class XorShift128 {private:uint32_t x, y, z, w;public:XorShift128() : x(123456789), y(362436069), z(521288629), w(88675123) { }uint32_t rnd() {uint32_t t = x ^ (x << 11);x = y;y = z;z = w;return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));}uint32_t rnd(const int n) {return rnd() % n;}uint32_t rnd(const int l, const int r) { // [l, r]return rnd() % (r - l + 1) + l;}};long long get_time() {struct timeval tv;gettimeofday(&tv, NULL);long long result = tv.tv_sec * 1000LL + tv.tv_usec / 1000LL;return result;}template<class T>ostream& operator<<(ostream& ostr, const vector<T>& vec) {ostr << "(";for (const T& val : vec) {ostr << val << ", ";}ostr << ")";return ostr;}mt19937 engine(890482);XorShift128 xor_shift_128;long long start;const int N = 20;const int MAX_TURNS = 1000;const int MAX_MOVES = 400;const int SH = 0, SW = 0, GH = N - 1, GW = N - 1;const double NO_WALL_PROB_INIT = 0.9999;const double NO_WALL = 1.0;const int NIL = -1;const int DH[4] = { -1, 0, 1, 0};const int DW[4] = { 0, -1, 0, 1};const char D_CHAR[4] = {'U', 'L', 'D', 'R'};int H, W, P;double prob = (double)P / 100.0;array<array<double, N>, N-1> no_wall_prob_ver;array<array<double, N-1>, N> no_wall_prob_hor;void init() {// inputcin >> H >> W >> P;// othersfor (int i = 0; i < N; ++i) {for (int j = 0; j < N - 1; ++j) {no_wall_prob_hor[i][j] = NO_WALL_PROB_INIT;no_wall_prob_ver[j][i] = NO_WALL_PROB_INIT;}}}bool in_grid(int h, int w) {return 0 <= h && h < N && 0 <= w && w < N;}void print_output(const vector<int>& output) {for (const int di: output) {cout << D_CHAR[di];}cout << endl;}double& get_no_wall_prob(int hi, int wi, int hj, int wj) {if (hi == hj) {// horizontal wallint mn = min(wi, wj);int mx = max(wi, wj);assert(mn + 1 == mx);return no_wall_prob_hor[hi][mn];} else if (wi == wj) {// vertical wallint mn = min(hi, hj);int mx = max(hi, hj);assert(mn + 1 == mx);return no_wall_prob_ver[mn][wi];} else {assert(false);}}void update_no_wall_prob(const vector<int>& output, const int end_turn) {int h = SH, w = SW;for (int ti = 0; ti < end_turn - 1; ++ti) {int di = output[ti];int nh = h + DH[di];int nw = w + DW[di];double& no_wall_prob = get_no_wall_prob(h, w, nh, nw);no_wall_prob = NO_WALL;h = nh;w = nw;}int di = output[end_turn - 1];int nh = h + DH[di];int nw = w + DW[di];double& no_wall_prob = get_no_wall_prob(h, w, nh, nw);if (no_wall_prob < NO_WALL) {no_wall_prob *= 1.0 - prob;}}int get_opposite_dir(int di) {return (di + 2) % 4;}const double INF = 1000000.0;array<int, 4> dir = {0, 1, 2, 3};vector<int> find_shortest_path() {array<array<double, N>, N> dists;array<array<int, N>, N> prev;for (int hi = 0; hi < N; ++hi) {for (int wi = 0; wi < N; ++wi) {dists[hi][wi] = INF;prev[hi][wi] = NIL;}}dists[SH][SW] = 0.0;priority_queue<tuple<double, int, int>> pq;pq.emplace(make_tuple(-0.0, SH, SW));while (!pq.empty()) {tuple<double, int, int> tpl = pq.top(); pq.pop();double d = -get<0>(tpl);int h = get<1>(tpl);int w = get<2>(tpl);if (dists[h][w] != d) {continue;}if (h == GH && w == GW) {break;}shuffle(dir.begin(), dir.end(), engine);for (const int di : dir) {int nh = h + DH[di];int nw = w + DW[di];if (!in_grid(nh, nw)) {continue;}const double no_wall_prob = get_no_wall_prob(h, w, nh, nw);double nd = d + (1.0 - no_wall_prob);if (nd < dists[nh][nw]) {dists[nh][nw] = nd;prev[nh][nw] = di;pq.emplace(make_tuple(-nd, nh, nw));}}}// restorevector<int> route;int h = GH;int w = GW;while (!(h == SH && w == SW)) {int di = prev[h][w];route.emplace_back(di);int opp_di = get_opposite_dir(di);h += DH[opp_di];w += DW[opp_di];}reverse(route.begin(), route.end());return route;}void solve() {for (int turn = 0; turn < MAX_TURNS; ++turn) {vector<int> output = find_shortest_path();assert(output.size() <= MAX_MOVES);print_output(output);int end_turn;cin >> end_turn;if (end_turn == -1) {break;}update_no_wall_prob(output, end_turn);}}int main() {start = get_time();init();solve();long long end = get_time();cerr << "time elapsed: " << end - start << endl;}