結果

問題 No.367 ナイトの転身
ユーザー maimai
提出日時 2016-04-29 23:36:26
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,469 bytes
コンパイル時間 927 ms
コンパイル使用メモリ 91,292 KB
実行使用メモリ 408,056 KB
最終ジャッジ日時 2024-04-15 06:04:57
合計ジャッジ時間 4,486 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
13,760 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 WA -
testcase_10 TLE -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:44:13: warning: 'sx' may be used uninitialized [-Wmaybe-uninitialized]
   44 |     qu.push(vector<int>{sx,sy,0,0,0});
      |             ^~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:26:9: note: 'sx' was declared here
   26 |     int sx,sy,gx,gy;
      |         ^~
main.cpp:44:13: warning: 'sy' may be used uninitialized [-Wmaybe-uninitialized]
   44 |     qu.push(vector<int>{sx,sy,0,0,0});
      |             ^~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:26:12: note: 'sy' was declared here
   26 |     int sx,sy,gx,gy;
      |            ^~
main.cpp:57:16: warning: 'gx' may be used uninitialized [-Wmaybe-uninitialized]
   57 |         k=abs(x-gx)+abs(y-gy);
      |               ~^~~
main.cpp:26:15: note: 'gx' was declared here
   26 |     int sx,sy,gx,gy;
      |               ^~
main.cpp:57:26: warning: 'gy' may be used uninitialized [-Wmaybe-uninitialized]
   57 |         k=abs(x-gx)+abs(y-gy);
      |                         ~^~~
main.cpp:26:18: note: 'gy' was declared here
   26 |     int sx,sy,gx,gy;
      |                  ^~

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <map>
#include <string>
#include <cstdio>
#include<functional>

using namespace std;

int mapf[501][501];
int dp[501][501][2];

int w,h;

inline bool inbox(int x,int y){
    return (0<=x && 0<=y && x<w && y<h);
}

int main(){
    int i,j,k,l,m,n;
    int x,y;
    char ch;
    
    int sx,sy,gx,gy;
    
    cin >> h>>w;
    
    for (y=0;y<h;y++){
        for (x=0;x<w;x++){
            while ((cin >> ch),(ch!='S'&&ch!='G'&&ch!='R'&&ch!='.'));
            if (ch=='S'){
                sx=x;sy=y;
            }
            if (ch=='G'){
                gx=x;gy=y;
            }
            mapf[x][y]=ch;
        }
    }
    
    priority_queue<vector<int>,vector<vector<int>>, function<bool(vector<int>&,vector<int>&)>> qu([](vector<int> &vl,vector<int> &vr){return vl[4]>vr[4];});
    qu.push(vector<int>{sx,sy,0,0,0});
    
    while (!qu.empty()){
        vector<int> e=qu.top();
        qu.pop();
        x=e[0];y=e[1];
        
        if (mapf[x][y]=='R') e[2]=!e[2];
        if (mapf[x][y]=='G'){
            cout << e[3] << endl;
            return 0;
        }
        dp[x][y][e[2]]=1;
        k=abs(x-gx)+abs(y-gy);
        e[3]++;
        if (!e[2]){
            if (inbox(x-2,y-1)&& !dp[x-2][y-1][0]) qu.push(vector<int>{x-2,y-1,e[2],e[3],-k});
            if (inbox(x-2,y+1)&& !dp[x-2][y+1][0]) qu.push(vector<int>{x-2,y+1,e[2],e[3],-k});
            if (inbox(x-1,y-2)&& !dp[x-1][y-2][0]) qu.push(vector<int>{x-1,y-2,e[2],e[3],-k});
            if (inbox(x-1,y+2)&& !dp[x-1][y+2][0]) qu.push(vector<int>{x-1,y+2,e[2],e[3],-k});
            if (inbox(x+2,y-1)&& !dp[x+2][y-1][0]) qu.push(vector<int>{x+2,y-1,e[2],e[3],-k});
            if (inbox(x+2,y+1)&& !dp[x+2][y+1][0]) qu.push(vector<int>{x+2,y+1,e[2],e[3],-k});
            if (inbox(x+1,y-2)&& !dp[x+1][y-2][0]) qu.push(vector<int>{x+1,y-2,e[2],e[3],-k});
            if (inbox(x+1,y+2)&& !dp[x+1][y+2][0]) qu.push(vector<int>{x+1,y+2,e[2],e[3],-k});
        }else{
            if (inbox(x-1,y-1)&& !dp[x-1][y-1][1]) qu.push(vector<int>{x-1,y-1,e[2],e[3],-k});
            if (inbox(x-1,y+1)&& !dp[x-1][y+1][1]) qu.push(vector<int>{x-1,y+1,e[2],e[3],-k});
            if (inbox(x+1,y-1)&& !dp[x+1][y-1][1]) qu.push(vector<int>{x+1,y-1,e[2],e[3],-k});
            if (inbox(x+1,y+1)&& !dp[x+1][y+1][1]) qu.push(vector<int>{x+1,y+1,e[2],e[3],-k});
        }
    }
            
    cout << -1 << endl;
    return 0;
}
0