結果
問題 | No.367 ナイトの転身 |
ユーザー | kongarishisyamo |
提出日時 | 2016-04-29 23:24:19 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 27 ms / 2,000 ms |
コード長 | 1,636 bytes |
コンパイル時間 | 646 ms |
コンパイル使用メモリ | 69,724 KB |
実行使用メモリ | 5,988 KB |
最終ジャッジ日時 | 2023-07-27 19:06:02 |
合計ジャッジ時間 | 2,007 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,272 KB |
testcase_01 | AC | 3 ms
5,272 KB |
testcase_02 | AC | 3 ms
5,372 KB |
testcase_03 | AC | 3 ms
5,436 KB |
testcase_04 | AC | 3 ms
5,392 KB |
testcase_05 | AC | 3 ms
5,388 KB |
testcase_06 | AC | 3 ms
5,372 KB |
testcase_07 | AC | 3 ms
5,504 KB |
testcase_08 | AC | 3 ms
5,272 KB |
testcase_09 | AC | 3 ms
5,620 KB |
testcase_10 | AC | 18 ms
5,988 KB |
testcase_11 | AC | 27 ms
5,968 KB |
testcase_12 | AC | 22 ms
5,496 KB |
testcase_13 | AC | 14 ms
5,792 KB |
testcase_14 | AC | 18 ms
5,608 KB |
testcase_15 | AC | 4 ms
5,308 KB |
testcase_16 | AC | 18 ms
5,500 KB |
testcase_17 | AC | 4 ms
5,532 KB |
testcase_18 | AC | 6 ms
5,388 KB |
testcase_19 | AC | 7 ms
5,424 KB |
testcase_20 | AC | 5 ms
5,336 KB |
testcase_21 | AC | 9 ms
5,424 KB |
testcase_22 | AC | 3 ms
5,616 KB |
testcase_23 | AC | 3 ms
5,316 KB |
testcase_24 | AC | 4 ms
5,308 KB |
testcase_25 | AC | 3 ms
5,368 KB |
testcase_26 | AC | 3 ms
5,268 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:71:15: warning: ‘gx’ may be used uninitialized in this function [-Wmaybe-uninitialized] int sy,sx,gy,gx; ^~ main.cpp:71:12: warning: ‘gy’ may be used uninitialized in this function [-Wmaybe-uninitialized] int sy,sx,gy,gx; ^~
ソースコード
#include<iostream> #include<string> #include<algorithm> #include<queue> using namespace std; #define MODE_B 0 #define MODE_M 1 #define INF 10000000 queue<int> qx,qy,qM; int dp[2][501][501]; string maze[501]; int H,W; void ini(){ for(int i=0;i<2;i++){ for(int j=0;j<501;j++){ for(int k=0;k<501;k++){ dp[i][j][k]=INF; } } } } void solve(){ int x=qx.front();qx.pop(); int y=qy.front();qy.pop(); int MODE=qM.front();qM.pop(); //cout<<x<<","<<y<<","<<qx.size()<<endl; int c=dp[MODE][y][x]; int dc,dx[8],dy[8]; if(MODE==MODE_M){ dc=4; dx[0]= 1,dx[1]= 1,dx[2]=-1,dx[3]=-1; dy[0]= 1,dy[1]=-1,dy[2]= 1,dy[3]=-1; } else{ dc=8; dx[0]= 2,dx[1]= 1,dx[2]=-1,dx[3]=-2,dx[4]= 2,dx[5]= 1,dx[6]=-1,dx[7]=-2; dy[0]= 1,dy[1]= 2,dy[2]= 2,dy[3]= 1,dy[4]=-1,dy[5]=-2,dy[6]=-2,dy[7]=-1; } for(int i=0;i<dc;i++){ int sx=x+dx[i]; int sy=y+dy[i]; if(sx>=0&&sx<W&&sy>=0&&sy<H){ if(maze[sy][sx]=='R'){ if(c+1<dp[1-MODE][sy][sx]){ dp[1-MODE][sy][sx]=c+1; qx.push(sx); qy.push(sy); qM.push(1-MODE); } } else{ if(c+1<dp[MODE][sy][sx]){ dp[MODE][sy][sx]=c+1; qx.push(sx); qy.push(sy); qM.push(MODE); } } } } } int main(){ cin>>H>>W; int sy,sx,gy,gx; for(int i=0;i<H;i++){ cin>>maze[i]; } for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ if(maze[i][j]=='S') sy=i,sx=j; if(maze[i][j]=='G') gy=i,gx=j; } } ini(); dp[MODE_B][sy][sx]=0; qx.push(sx); qy.push(sy); qM.push(MODE_B); while(!qx.empty()){ solve(); } if(dp[0][gy][gx]==INF&&dp[1][gy][gx]==INF) cout<<"-1"<<endl; else cout<<min(dp[0][gy][gx],dp[1][gy][gx])<<endl; }