結果

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

ソースコード

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 int min_p = 5;
const int max_p = 12;
int H, W, poss;
double p, back;
double h[20][21], v[21][20];
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] < 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;
}
int main(){
    cin >> H >> W >> poss;
    assert(H == 20 && W == 20);
    assert(min_p <= poss && poss <= max_p);
    p = poss;
    p /= 100;
    back = p * 5.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] = 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] > 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;
        }
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0