#include #include using namespace std; void debug() { std::cerr << std::endl; std::cerr << "↑ [line:" << __LINE__ << "]" << std::endl; } template void debug(Head&& head, Tail&&... tail) { std::cerr << head << ", "; debug(std::forward(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 ostream& operator<<(ostream& ostr, const vector& 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 NOT_ARRIVED = 500.0; 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; array, N> no_wall_prob_ver; array, N - 1> no_wall_prob_hor; void init() { // input cin >> H >> W >> P; // others for (int i = 0; i < N; ++i) { for (int j = 0; j < N - 1; ++j) { no_wall_prob_ver[i][j] = NOT_ARRIVED; no_wall_prob_hor[j][i] = NOT_ARRIVED; } } prob = (double)P / 100.0; } bool in_grid(int h, int w) { return 0 <= h && h < N && 0 <= w && w < N; } void print_output(const vector& output) { for (const int di: output) { cerr << D_CHAR[di]; cout << D_CHAR[di]; } cerr << endl; cout << endl; } double& get_no_wall_prob(int hi, int wi, int hj, int wj) { if (hi == hj) { // vertical wall int mn = min(wi, wj); int mx = max(wi, wj); assert(mn + 1 == mx); return no_wall_prob_ver[hi][mn]; } else if (wi == wj) { // horizontal wall int mn = min(hi, hj); int mx = max(hi, hj); assert(mn + 1 == mx); return no_wall_prob_hor[mn][wi]; } else { assert(false); } } void update_no_wall_prob(const vector& 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 == NOT_ARRIVED) { no_wall_prob = NO_WALL; } if (no_wall_prob <= NO_WALL) { no_wall_prob *= prob; } // for (int hi = 0; hi < N; ++hi) { // for (int wi = 0; wi < N - 1; ++wi) { // cerr << "ver (" << hi << ", " << wi << "): " << no_wall_prob_ver[hi][wi] << endl; // } // } // for (int hi = 0; hi < N - 1; ++hi) { // for (int wi = 0; wi < N; ++wi) { // cerr << "hor (" << hi << ", " << wi << "): " << no_wall_prob_hor[hi][wi] << endl; // } // } } int get_opposite_dir(int di) { return (di + 2) % 4; } const double INF = 1000000.0; array dir = {0, 1, 2, 3}; vector find_shortest_path() { array, N> dists; array, 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> pq; pq.emplace(make_tuple(-0.0, SH, SW)); while (!pq.empty()) { tuple 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 + (NOT_ARRIVED - no_wall_prob); if (nd < dists[nh][nw]) { dists[nh][nw] = nd; prev[nh][nw] = di; pq.emplace(make_tuple(-nd, nh, nw)); } } } // restore vector 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) { cerr << "turn: " << turn << endl; vector 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; }