結果

問題 No.367 ナイトの転身
ユーザー sekiya9311sekiya9311
提出日時 2016-04-30 01:36:53
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 2,486 bytes
コンパイル時間 1,369 ms
コンパイル使用メモリ 111,744 KB
実行使用メモリ 814,816 KB
最終ジャッジ日時 2024-10-04 23:48:59
合計ジャッジ時間 4,809 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,824 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 3 ms
6,820 KB
testcase_07 AC 2 ms
6,820 KB
testcase_08 AC 2 ms
6,820 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 60 ms
17,664 KB
testcase_11 MLE -
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:80:22: warning: 'gw' may be used uninitialized [-Wmaybe-uninitialized]
   80 |         if(map[gh][gw][0] || map[gh][gw][1]) break;
      |                      ^
main.cpp:40:18: note: 'gw' was declared here
   40 |     int sh,sw,gh,gw;
      |                  ^~
main.cpp:80:18: warning: 'gh' may be used uninitialized [-Wmaybe-uninitialized]
   80 |         if(map[gh][gw][0] || map[gh][gw][1]) break;
      |                  ^
main.cpp:40:15: note: 'gh' was declared here
   40 |     int sh,sw,gh,gw;
      |               ^~

ソースコード

diff # 

#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <numeric>

#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define RREP(i,a) for(int (i)=(a)-1;(i)>=0;(i)--)
#define FORR(i,a,b) for(int (i)=(a)-1;(i)>=(b);(i)--)

typedef long long LL;
typedef unsigned long long ULL;

using namespace std;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int kh[8] = {1,2,-1,-2,1,2,-1,-2};
int kw[8] = {2,1,-2,-1,-2,-1,2,1};
int bh[4] = {1, -1, -1, 1};
int bw[4] = {1, 1, -1, -1};

int main(){
    int H,W; cin>>H>>W; //y=h,x=w
    int sh,sw,gh,gw;
    vector<string> s(H);
    REP(i,H){
        cin>>s[i];
        if(s[i].find("S")!=-1){
            sh=i; sw=s[i].find("S");
        }
        if(s[i].find("G")!=-1){
            gh=i; gw=s[i].find("G");
        }
    }
    //long map[H][W][2]; 最後1ならナイト 0ならミニビショップ
    vector<vector<vector<long>>> map(H,vector<vector<long>>(W,vector<long>(2,0)));
    queue<int> h; queue<int> w; queue<bool> flag;
    h.push(sh); w.push(sw); flag.push(true);
    while(!h.empty()){
        int hh,ww; bool f;
        hh=h.front(); ww=w.front(); f=flag.front();
        h.pop(); w.pop(); flag.pop();
        if(f){
            REP(i,8){
                int mh=hh+kh[i],mw=ww+kw[i],d=1;
                if(mh<0 || mw<0 || mh>=H || mw>=W) continue;
                if(map[mh][mw][d]&&s[mh][mw]!='R') continue;
                if(s[mh][mw]=='R') {flag.push(false); d=0;}
                else flag.push(true);
                map[mh][mw][d]=map[hh][ww][1]+1;
                h.push(mh); w.push(mw);
            }
        }else{
            REP(i,4){
                int mh=hh+bh[i],mw=ww+bw[i],d=0;
                if(mh<0 || mw<0 || mh>=H || mw>=W) continue;
                if(map[mh][mw][d]&&s[mh][mw]!='R') continue;
                if(s[mh][mw]=='R') {flag.push(true); d=1;}
                else flag.push(false);
                map[mh][mw][d]=map[hh][ww][0]+1;
                h.push(mh); w.push(mw);
            }
        }
        if(map[gh][gw][0] || map[gh][gw][1]) break;
    }
    if(!map[gh][gw][0] && !map[gh][gw][1]) cout<<-1<<endl;
    else cout<<max(map[gh][gw][0],map[gh][gw][1])<<endl;
}
0