結果

問題 No.367 ナイトの転身
ユーザー rapurasurapurasu
提出日時 2016-07-28 17:30:48
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 66 ms / 2,000 ms
コード長 2,854 bytes
コンパイル時間 1,784 ms
コンパイル使用メモリ 171,056 KB
実行使用メモリ 18,304 KB
最終ジャッジ日時 2024-04-24 10:34:26
合計ジャッジ時間 3,120 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
15,360 KB
testcase_01 AC 11 ms
15,360 KB
testcase_02 AC 11 ms
15,360 KB
testcase_03 AC 11 ms
15,232 KB
testcase_04 AC 11 ms
15,232 KB
testcase_05 AC 11 ms
15,360 KB
testcase_06 AC 13 ms
18,304 KB
testcase_07 AC 12 ms
15,360 KB
testcase_08 AC 12 ms
15,360 KB
testcase_09 AC 11 ms
15,232 KB
testcase_10 AC 44 ms
18,176 KB
testcase_11 AC 66 ms
18,304 KB
testcase_12 AC 35 ms
17,280 KB
testcase_13 AC 33 ms
17,152 KB
testcase_14 AC 33 ms
17,152 KB
testcase_15 AC 13 ms
17,152 KB
testcase_16 AC 31 ms
17,536 KB
testcase_17 AC 14 ms
16,000 KB
testcase_18 AC 16 ms
16,128 KB
testcase_19 AC 17 ms
16,000 KB
testcase_20 AC 14 ms
16,000 KB
testcase_21 AC 18 ms
16,128 KB
testcase_22 AC 11 ms
15,232 KB
testcase_23 AC 12 ms
15,488 KB
testcase_24 AC 12 ms
15,488 KB
testcase_25 AC 13 ms
15,616 KB
testcase_26 AC 11 ms
15,232 KB
権限があれば一括ダウンロードができます

ソースコード

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