結果
問題 | No.5006 Hidden Maze |
ユーザー |
|
提出日時 | 2022-06-06 11:42:33 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 81 ms / 2,000 ms |
コード長 | 1,892 bytes |
コンパイル時間 | 2,959 ms |
実行使用メモリ | 22,856 KB |
スコア | 67,823 |
平均クエリ数 | 322.77 |
最終ジャッジ日時 | 2022-06-12 13:32:55 |
合計ジャッジ時間 | 11,034 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#include<bits/stdc++.h>using namespace std;int h,w,p;int ask(string &s){cout << s << '\n';fflush(stdout);int res;cin >> res;return res;}string dch="UDLR";int dx4[4]={-1,1,0,0};int dy4[4]={0,0,-1,1};int cvrt[256];int getID(int fx,int fy,int d){if(d==0){fx--;}if(d==2){fy--;}if(d<=1){return fx*20+fy;}return (20*20)+fx*20+fy;}int fix[1024]={0};double prob[1024];double iniprob,hitwall;using pdi=pair<double,int>;string dijkstra(){vector<double> d(512,1e9);vector<int> mem(512,0);priority_queue<pdi,vector<pdi>,greater<pdi>> pq;d[0]=0;mem[0]=-1;pq.push({0,0});while(!pq.empty()){pdi od=pq.top();pq.pop();if(d[od.second]>od.first){continue;}int x=od.second/w;int y=od.second%w;for(int i=0;i<4;i++){int nx=x+dx4[i];int ny=y+dy4[i];if(!(0<=nx && nx<h)){continue;}if(!(0<=ny && ny<w)){continue;}double cur=prob[getID(x,y,i)];int nv=nx*w+ny;if(d[nv]>(od.first+cur)){d[nv]=(od.first+cur);mem[nv]=i;pq.push({d[nv],nv});}}}string res;int cx=h-1,cy=w-1;while(cx>0 || cy>0){int cd=mem[cx*w+cy];res.push_back(dch[cd]);cx-=dx4[cd];cy-=dy4[cd];}reverse(res.begin(),res.end());return res;}void feedback(string &path,int hands){int x=0,y=0;for(int i=0;i<=hands;i++){int d=cvrt[path[i]];int id=getID(x,y,d);if(i!=hands){fix[id]=1;}if(fix[id]){prob[id]=iniprob;}else{prob[id]+=hitwall;}x+=dx4[d];y+=dy4[d];}}int main(){for(int i=0;i<4;i++){cvrt[dch[i]]=i;}cin >> h >> w >> p;iniprob=-log(((double)(100-p))/100.0);hitwall=-log(((double)p)/100.0);for(int i=0;i<1024;i++){prob[i]=iniprob;}while(1){string cask=dijkstra();int cres=ask(cask);if(cres==-1){break;}feedback(cask,cres);}return 0;}