結果
問題 | No.367 ナイトの転身 |
ユーザー |
![]() |
提出日時 | 2024-08-19 10:35:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 27 ms / 2,000 ms |
コード長 | 1,522 bytes |
コンパイル時間 | 2,034 ms |
コンパイル使用メモリ | 175,112 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-08-19 10:35:47 |
合計ジャッジ時間 | 3,465 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
#include<bits/stdc++.h> #define PII pair<int,int> using namespace std; const int N=505,INF=0x3f3f3f3f; int h,w; char s[N][N]; int d[N][N][2]; int sx,sy,gx,gy; int dx8[8]={2,2,1,1,-1,-1,-2,-2},dy8[8]={1,-1,2,-2,2,-2,1,-1}; int dx4[4]={1,1,-1,-1},dy4[4]={1,-1,-1,1}; int bfs(){ queue<pair<int,PII>>que; for(int i=0;i<h;i++) for(int j=0;j<w;j++) for(int k=0;k<2;k++) d[i][j][k]=INF; que.push(make_pair(1,PII(sx,sy))); d[sx][sy][1]=0; while(!que.empty()){ int node=que.front().first; PII p=que.front().second; que.pop(); if(p.first==gx&&p.second==gy)break; if(node==1){ for(int k=0;k<8;k++){ int nx=p.first+dx8[k],ny=p.second+dy8[k]; int nm=node^(s[nx][ny]=='R'); if(nx<0||nx>=h||ny<0||ny>=w)continue; if(d[nx][ny][nm]!=INF)continue; que.push(make_pair(nm,PII(nx,ny))); d[nx][ny][nm]=d[p.first][p.second][node]+1; } } else{ for(int i=0;i<4;i++){ int nx=p.first+dx4[i],ny=p.second+dy4[i]; int nm=node^(s[nx][ny]=='R'); if(nx<0||nx>=h||ny<0||ny>=w)continue; if(d[nx][ny][nm]!=INF)continue; que.push(make_pair(nm,PII(nx,ny))); d[nx][ny][nm]=d[p.first][p.second][node]+1; } } } return min(d[gx][gy][0],d[gx][gy][1]); } int main(){ //freopen("knight.in","r",stdin); //freopen("knight.out","w",stdout); cin>>h>>w; for(int i=0;i<h;i++){ string str;cin>>str; for(int j=0;j<w;j++){ s[i][j]=str[j]; if(s[i][j]=='S')sx=i,sy=j; else if(s[i][j]=='G')gx=i,gy=j; } } int ans=bfs(); if(ans==INF)ans=-1; cout<<ans; return 0; }