結果
問題 |
No.367 ナイトの転身
|
ユーザー |
![]() |
提出日時 | 2016-07-28 17:30:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 62 ms / 2,000 ms |
コード長 | 2,854 bytes |
コンパイル時間 | 1,690 ms |
コンパイル使用メモリ | 175,428 KB |
実行使用メモリ | 20,252 KB |
最終ジャッジ日時 | 2024-11-06 18:11:53 |
合計ジャッジ時間 | 3,028 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define INF 1000000000 #define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++) #define MAX_V 500000 struct edge {int to,cost;}; typedef pair<int,int> P; //firstは最短距離,secondは頂点の番号 int V; vector<edge> G[MAX_V]; int d[MAX_V]; int H,W; int sx,sy; int gx,gy; int check[501][501]; int dp[2][501][501]; int ni_x[8]={-2,-1,1,2,-2,-1,1,2}; int ni_y[8]={1,2,2,1,-1,-2,-2,-1}; int bi_x[4]={-1,1,-1,1}; int bi_y[4]={1,1,-1,-1}; struct gli{ int cost; int c;//1ナイト0ミニビショップ int x; int y; }; bool operator <(const gli& g,const gli& g2){ return g.cost<g2.cost; } bool operator >(const gli& g,const gli& g2){ return g.cost>g2.cost; } bool check_range(int x,int y){ if(x<0||x>=H||y<0||y>=W)return false; return true; } void dijkstra(int x,int y){ priority_queue<gli,vector<gli>,greater<gli> > que; gli g1={0,1,x,y}; //gli g2={0,1,x,y}; dp[1][x][y]=0; que.push(g1); //que.push(g2); while(!que.empty()){ gli g=que.top();que.pop(); if(dp[g.c][g.x][g.y]<g.cost)continue; //cout<<g.cost<<endl; if(g.c==1){ REP(i,8){ int xx=ni_x[i]+g.x; int yy=ni_y[i]+g.y; int c=g.c; if(check_range(xx,yy)){ if(check[xx][yy]==1)c=1-c; if(dp[c][xx][yy]>g.cost+1){ dp[c][xx][yy]=g.cost+1; gli gg={g.cost+1,c,xx,yy}; que.push(gg); } } } }else{ REP(i,4){ int xx=bi_x[i]+g.x; int yy=bi_y[i]+g.y; int c=g.c; if(check_range(xx,yy)){ if(check[xx][yy]==1)c=1-c; if(dp[c][xx][yy]>g.cost+1){ dp[c][xx][yy]=g.cost+1; gli gg={g.cost+1,c,xx,yy}; que.push(gg); } } } } } } int main(){ cin>>H>>W; REP(i,H){ REP(j,W){ check[i][j]=0; } } REP(i,2){ REP(j,H){ REP(k,W){ dp[i][j][k]=INF; } } } REP(i,H){ string s; cin>>s; REP(j,W){ if(s[j]=='R'){ check[i][j]=1; } if(s[j]=='S'){ sx=i;sy=j; } if(s[j]=='G'){ gx=i;gy=j; } } } dijkstra(sx,sy); /* REP(i,2){ REP(j,H){ REP(k,W){ cout<<dp[i][j][k]<<" "; } cout<<endl; } cout<<endl; }*/ int ans=min(dp[0][gx][gy],dp[1][gx][gy]); if(ans==INF){ cout<<-1<<endl; }else{ cout<<ans<<endl; } }