結果

問題 No.5006 Hidden Maze
ユーザー platinum
提出日時 2022-06-12 00:13:20
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 69 ms / 2,000 ms
コード長 4,253 bytes
コンパイル時間 1,848 ms
実行使用メモリ 22,868 KB
スコア 78,002
平均クエリ数 220.98
最終ジャッジ日時 2022-06-12 13:36:22
合計ジャッジ時間 9,165 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using LL = long long;
using P = pair<int,int>;
using vv = vector<vector<int>>;
const int INF = (int)1e9;
const LL LINF = (LL)1e18;
const double eps = 1e-5;
const int min_p = 6;
const int max_p = 15;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
string dir = "UDLR";
double h[20][21], v[21][20];
int H, W, poss;
double p;
/*
string bfs(){
    int dist[20][20];
    rep(i,20){
        rep(j,20) dist[i][j] = -1;
    }
    dist[0][0] = 0;
    queue<P> q;
    q.emplace(0, 0);
    while(!q.empty()){
        pair<int,int> p = q.front(); q.pop();
        int y = p.first, x = p.second;
        int d = dist[y][x];
        if(v[y][x] < 0.5 && dist[y-1][x] == -1){
            dist[y-1][x] = d + 1;
            q.emplace(y - 1, x);
        }
        if(v[y+1][x] < 0.5 && dist[y+1][x] == -1){
            dist[y+1][x] = d + 1;
            q.emplace(y + 1, x);
        }
        if(h[y][x] < 0.5 && dist[y][x-1] == -1){
            dist[y][x-1] = d + 1;
            q.emplace(y, x - 1);
        }
        if(h[y][x+1] < 0.5 && dist[y][x+1] == -1){
            dist[y][x+1] = d + 1;
            q.emplace(y, x + 1);
        }
    }
    string res;
    int y = 19, x = 19;
    if(dist[y][x] == -1){
        rep(i,19) res.push_back('R');
        rep(i,19) res.push_back('D');
        return res;
    }
    while(y != 0 || x != 0){
        int d = dist[y][x];
        if(v[y][x] < 0.5 && dist[y-1][x] == d - 1){
            res.push_back('D');
            y--;
        }
        else if(v[y+1][x] < 0.5 && dist[y+1][x] == d - 1){
            res.push_back('U');
            y++;
        }
        else if(h[y][x] < 0.5 && dist[y][x-1] == d - 1){
            res.push_back('R');
            x--;
        }
        else if(h[y][x+1] < 0.5 && dist[y][x+1] == d - 1){
            res.push_back('L');
            x++;
        }
        else break;
    }
    reverse(res.begin(), res.end());
    return res;
}
*/
struct node{
    int y, x;
    double d;
    node(int y, int x, double d) : y(y), x(x), d(d) {}
    bool operator> (const node &u) const{
        return d > u.d;
    }
};
string dijkstra(){
    double dist[20][20];
    rep(i,20){
        rep(j,20) dist[i][j] = INF;
    }
    char par[20][20];
    dist[0][0] = 0;
    priority_queue<node,vector<node>,greater<>> pq;
    pq.emplace(0, 0, 0);
    while(!pq.empty()){
        node u = pq.top(); pq.pop();
        if(dist[u.y][u.x] != u.d) continue;
        rep(k,4){
            int ny = u.y + dy[k], nx = u.x + dx[k];
            if(ny < 0 || ny >= 20) continue;
            if(nx < 0 || nx >= 20) continue;
            double e = 0;
            if(k == 0) e = 1.0 / (1.0 - v[u.y][u.x]);
            else if(k == 1) e = 1.0 / (1.0 - v[u.y+1][u.x]);
            else if(k == 2) e = 1.0 / (1.0 - h[u.y][u.x]);
            else e = 1.0 / (1.0 - h[u.y][u.x+1]);
            double nd = u.d + e;
            if(dist[ny][nx] <= nd) continue;
            pq.emplace(ny, nx, nd);
            dist[ny][nx] = nd;
            par[ny][nx] = dir[k];
        }
    }
    int now_y = 19, now_x = 19;
    string res;
    while(now_y != 0 || now_x != 0){
        char c = par[now_y][now_x];
        res += c;
        if(c == 'U') now_y++;
        else if(c == 'D') now_y--;
        else if(c == 'L') now_x++;
        else now_x--;
    }
    reverse(res.begin(), res.end());
    return res;
}
double update(double now_p){
    if(now_p < eps) return now_p;
    double wall_p = now_p + (1.0 - now_p) * p;
    return now_p / wall_p;
}
int main(){
    cin >> H >> W >> poss;
    assert(H == 20 && W == 20);
    assert(min_p <= poss && poss <= max_p);
    p = poss;
    p /= 100.0;
    rep(i,20){
        h[i][0] = 1.0;
        h[i][20] = 1.0;
    }
    rep(j,20){
        v[0][j] = 1.0;
        v[20][j] = 1.0;
    }
    rep(i,20){
        rep(j,19) h[i][j+1] = 0.5;
    }
    rep(i,19){
        rep(j,20) v[i+1][j] = 0.5;
    }
    rep(trial,1001){
        //string ans = bfs();
        string ans = dijkstra();
        cout << ans << endl;
        int res;
        cin >> res;
        if(res == -1){
            cerr << "score = " << 1000 - trial << endl;
            break;
        }
        int y = 0, x = 0;
        int siz = ans.size();
        rep(i,res){
            char c = ans[i];
            if(c == 'U') v[y][x] = 0, y--;
            if(c == 'D') v[y+1][x] = 0, y++;
            if(c == 'L') h[y][x] = 0, x--;
            if(c == 'R') h[y][x+1] = 0, x++;
        }
        if(res < siz){
            char c = ans[res];
            /*
            if(c == 'U' && v[y][x] > eps) v[y][x] = 1.0 - (1.0 - v[y][x]) * p;
            if(c == 'D' && v[y+1][x] > eps) v[y+1][x] = 1.0 - (1.0 - v[y+1][x]) * p;
            if(c == 'L' && h[y][x] > eps) h[y][x] = 1.0 - (1.0 - h[y][x]) * p;
            if(c == 'R' && h[y][x+1] > eps) h[y][x+1] = 1.0 - (1.0 - h[y][x+1]) * p;
            */
            if(c == 'U') v[y][x] = update(v[y][x]);
            if(c == 'D') v[y+1][x] = update(v[y+1][x]);
            if(c == 'L') h[y][x] = update(h[y][x]);
            if(c == 'R') h[y][x+1] = update(h[y][x+1]);
        }
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0