結果

問題 No.5006 Hidden Maze
ユーザー tails
提出日時 2022-06-12 17:37:09
言語 cLay
(20241019-1)
結果
AC  
実行時間 60 ms / 2,000 ms
コード長 1,560 bytes
コンパイル時間 2,715 ms
実行使用メモリ 22,868 KB
スコア 75,598
平均クエリ数 245.02
最終ジャッジ日時 2022-06-12 17:37:19
合計ジャッジ時間 9,936 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff # 

//interactive

char sy[20][20];
char sx[20][20];
ll ey[20][20],ey0[20][20];
ll ex[20][20],ex0[20][20];
ll d[20][20];

ll cost_c=100000;
ll cost_i=800;
ll cost_w=1600000;

{
	rd_ll(); // H
	rd_ll(); // W
	rd_ll(); // p
	
	rep(y,20){
		rep(x,20){
			ey[y][x]=(ey0[y][x]=cost_c+abs(y*2+1-x*2))+cost_i;
			ex[y][x]=(ex0[y][x]=cost_c+abs(y*2-x*2-1))+cost_i;
		}
	}

	DijkstraHeap<ll> h;
	h.walloc(400);
	while(true){
		{
			h.init(400);
			h.change(19*20+19,-0);
			while(h.size){
				ll k=h.pop();
				ll v=h.val[k];
				ll y=k/20;
				ll x=k%20;
				d[y][x]=v;
				v&=~3l;
				if(y!= 0) h.change(k-20,v+ey[y-1][x]*4+0);
				if(y!=19) h.change(k+20,v+ey[y-0][x]*4+1);
				if(x!= 0) h.change(k- 1,v+ex[y][x-1]*4+2);
				if(x!=19) h.change(k+ 1,v+ex[y][x-0]*4+3);
			}
		}
		char p[401];
		{
			ll l=0;
			ll x=0;
			ll y=0;
			while(!(y==19&&x==19)){
				ll c=d[y][x]&3;
				p[l++]="DURL"[c];
				y+=(c==0)-(c==1);
				x+=(c==2)-(c==3);
			}
			p[l]=0;
			wt(p);
		}
		{
			ll@r;
			if(r<0) exit(0);
			ll x=0;
			ll y=0;
			rep(i,r){
				ll c=p[i];
				if(c=='U') if(!sy[--y][x]) sy[y-0][x]=1,ey[y-0][x]=ey0[y-0][x];
				if(c=='D') if(!sy[y++][x]) sy[y-1][x]=1,ey[y-1][x]=ey0[y-1][x];
				if(c=='L') if(!sx[y][--x]) sx[y][x-0]=1,ex[y][x-0]=ex0[y][x-0];
				if(c=='R') if(!sx[y][x++]) sx[y][x-1]=1,ex[y][x-1]=ex0[y][x-1];
			}
			{
				ll c=p[r];
				if(c=='U') if(!sy[--y][x]) ey[y-0][x]+=cost_w;
				if(c=='D') if(!sy[y++][x]) ey[y-1][x]+=cost_w;
				if(c=='L') if(!sx[y][--x]) ex[y][x-0]+=cost_w;
				if(c=='R') if(!sx[y][x++]) ex[y][x-1]+=cost_w;
			}
		}
	}
}
0