結果

問題 No.367 ナイトの転身
ユーザー rapurasu
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

 #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;
    }
}
0