結果
問題 | No.1323 うしらずSwap |
ユーザー |
![]() |
提出日時 | 2020-12-22 18:23:56 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 216 ms / 3,000 ms |
コード長 | 1,713 bytes |
コンパイル時間 | 257 ms |
コンパイル使用メモリ | 34,048 KB |
実行使用メモリ | 25,216 KB |
最終ジャッジ日時 | 2024-11-15 09:44:39 |
合計ジャッジ時間 | 5,536 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
コンパイルメッセージ
main.c:58:1: warning: return type defaults to 'int' [-Wimplicit-int] 58 | main(){ | ^~~~ main.c: In function 'main': main.c:112:9: warning: implicit declaration of function 'printf' [-Wimplicit-function-declaration] 112 | printf("%d\n",z>=INF?-1:z); | ^~~~~~ main.c:1:1: note: include '<stdio.h>' or provide a declaration of 'printf' +++ |+#include <stdio.h> 1 | #pragma GCC optimize("Ofast") main.c:112:9: warning: incompatible implicit declaration of built-in function 'printf' [-Wbuiltin-declaration-mismatch] 112 | printf("%d\n",z>=INF?-1:z); | ^~~~~~ main.c:112:9: note: include '<stdio.h>' or provide a declaration of 'printf'
ソースコード
#pragma GCC optimize("Ofast") #pragma GCC target("avx2") char*mmap(); char*rp; #define RD(v) v=0;{int _c;while(_c=*rp++-48,_c>=0)v=v*10+_c;} int wy,wx,ay,ax,by,bx; static inline int s(int y,int x){ return rp[y*(wx+1)+x]=='.'; } #define INF (1<<24) int dp1[1333][1333]; int dp2[1333][1333]; int dp3[1333][1333]; struct{int y,x,d;} q[1<<16]; int qr,qw; static inline void enq(int y,int x,int d){ q[qw].y=y; q[qw].x=x; q[qw].d=d; qw=(qw+1)&(1<<16)-1; } void bfs(int y,int x,int ty,int tx,int dp[1333][1333]){ for(int y=0;y<wy;++y){ for(int x=0;x<wx;++x){ dp[y][x]=INF; } } qr=qw=0; int d=0; enq(y,x,d); while(qr!=qw){ y=q[qr].y; x=q[qr].x; d=q[qr].d; qr=(qr+1)&(1<<16)-1; if(s(y,x)&&dp[y][x]==INF){ dp[y][x]=d; if(!(y==ty&&x==tx)){ ++d; enq(y-1,x,d); enq(y+1,x,d); enq(y,x-1,d); enq(y,x+1,d); } } } } main(){ rp=mmap(0l,1l<<28,1,2,0,0ll); RD(wy); RD(wx); RD(ay);--ay; RD(ax);--ax; RD(by);--by; RD(bx);--bx; bfs(ay,ax,0,0,dp1); bfs(by,bx,0,0,dp2); bfs(ay,ax,by,bx,dp3); int len=dp1[by][bx]; int z=INF; { int n=0; for(int y=0;y<wy;++y){ for(int x=0;x<wx;++x){ if(s(y,x)){ int d=dp1[y][x]+dp2[y][x]; if(d==len&&!(y==ay&&x==ax)&&!(y==by&&x==bx)){ ++n; d-=1; } if(s(y-1,x)+s(y+1,x)+s(y,x-1)+s(y,x+1)>2){ d+=2; z=z<=d?z:d; } } } } if(n>len-1){ z=len; } } z*=2; { int d; d=dp3[by-1][bx]; if(d!=len-1&&z>len+d+1){ z=len+d+1; } d=dp3[by+1][bx]; if(d!=len-1&&z>len+d+1){ z=len+d+1; } d=dp3[by][bx-1]; if(d!=len-1&&z>len+d+1){ z=len+d+1; } d=dp3[by][bx+1]; if(d!=len-1&&z>len+d+1){ z=len+d+1; } } printf("%d\n",z>=INF?-1:z); }