結果

問題 No.367 ナイトの転身
コンテスト
ユーザー sekiya9311
提出日時 2016-04-30 00:13:16
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 2,284 bytes
コンパイル時間 1,088 ms
コンパイル使用メモリ 113,016 KB
実行使用メモリ 691,792 KB
最終ジャッジ日時 2024-10-04 23:23:33
合計ジャッジ時間 4,484 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 MLE * 1 -- * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:80:19: warning: 'gw' may be used uninitialized [-Wmaybe-uninitialized]
   80 |     if(!map[gh][gw]) map[gh][gw]=-1;
      |                   ^
main.cpp:39:18: note: 'gw' was declared here
   39 |     int sh,sw,gh,gw;
      |                  ^~
main.cpp:80:15: warning: 'gh' may be used uninitialized [-Wmaybe-uninitialized]
   80 |     if(!map[gh][gw]) map[gh][gw]=-1;
      |               ^
main.cpp:39:15: note: 'gh' was declared here
   39 |     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>

#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");
        }else if(s[i].find("G")!=-1){
            gh=i; gw=s[i].find("G");
        }
    }
    //long map[H][W];
    vector<vector<long>> map(H,vector<long>(W,0));
    vector<vector<int>> fmap(H,vector<int>(W,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];
                if(mh<0 || mw<0 || mh>=H || mw>=W) continue;
                if(map[mh][mw]&&s[mh][mw]!='R') continue;
                if(s[mh][mw]=='R') flag.push(false);
                else flag.push(true);
                map[mh][mw]=map[hh][ww]+1;
                h.push(mh); w.push(mw);
            }
        }else{
            REP(i,4){
                int mh=hh+bh[i],mw=ww+bw[i];
                if(mh<0 || mw<0 || mh>=H || mw>=W) continue;
                if(map[mh][mw]&&s[mh][mw]!='R') continue;
                if(s[mh][mw]=='R') flag.push(true);
                else flag.push(false);
                map[mh][mw]=map[hh][ww]+1;
                h.push(mh); w.push(mw);
            }
        }
    }
    if(!map[gh][gw]) map[gh][gw]=-1;
    cout<<map[gh][gw]<<endl;
}
0