結果

問題 No.5006 Hidden Maze
ユーザー platinum
提出日時 2022-06-06 15:02:50
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,730 bytes
コンパイル時間 1,870 ms
実行使用メモリ 22,888 KB
スコア 35,875
平均クエリ数 142.25
最終ジャッジ日時 2022-06-12 13:33:32
合計ジャッジ時間 22,392 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50 RE * 50
権限があれば一括ダウンロードができます

ソースコード

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 double init_p = 0.20;
const double back = 0.80;
const int min_p = 3;
const int max_p = 10;
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> pa = q.front(); q.pop();
        int y = pa.first, x = pa.second;
        int d = dist[y][x];
        if(v[y][x] < back && dist[y-1][x] == -1){
            dist[y-1][x] = d + 1;
            q.emplace(y - 1, x);
        }
        if(v[y+1][x] < back && dist[y+1][x] == -1){
            dist[y+1][x] = d + 1;
            q.emplace(y + 1, x);
        }
        if(h[y][x] < back && dist[y][x-1] == -1){
            dist[y][x-1] = d + 1;
            q.emplace(y, x - 1);
        }
        if(h[y][x+1] < back && 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] < back && dist[y-1][x] == d - 1){
            res.push_back('D');
            y--;
        }
        else if(v[y+1][x] < back && dist[y+1][x] == d - 1){
            res.push_back('U');
            y++;
        }
        else if(h[y][x] < back && dist[y][x-1] == d - 1){
            res.push_back('R');
            x--;
        }
        else if(h[y][x+1] < back && dist[y][x+1] == d - 1){
            res.push_back('L');
            x++;
        }
        else break;
    }
    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;
    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] = init_p;
    }
    rep(i,19){
        rep(j,20) v[i+1][j] = init_p;
    }
    rep(trial,1001){
        string ans = bfs();
        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] = 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