結果

問題 No.367 ナイトの転身
コンテスト
ユーザー mai
提出日時 2016-04-30 14:07:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,179 bytes
コンパイル時間 992 ms
コンパイル使用メモリ 85,488 KB
実行使用メモリ 777,188 KB
最終ジャッジ日時 2024-10-05 00:02:01
合計ジャッジ時間 4,670 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 MLE * 1 -- * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:40:13: warning: 'sy' may be used uninitialized [-Wmaybe-uninitialized]
   40 |     qu.push(vector<int>{sx,sy,0,0});
      |             ^~~~~~~~~~~~~~~~~~~~~~
main.cpp:25:12: note: 'sy' was declared here
   25 |     int sx,sy;
      |            ^~
main.cpp:40:13: warning: 'sx' may be used uninitialized [-Wmaybe-uninitialized]
   40 |     qu.push(vector<int>{sx,sy,0,0});
      |             ^~~~~~~~~~~~~~~~~~~~~~
main.cpp:25:9: note: 'sx' was declared here
   25 |     int sx,sy;
      |         ^~

ソースコード

diff # 

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

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;
    
    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;
            }
            mapf[x][y]=ch;
        }
    }
    
    queue<vector<int>> qu;
    qu.push(vector<int>{sx,sy,0,0});
    
    while (!qu.empty()){
        vector<int> &e=qu.front();
        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;
        e[3]++;
        if (!e[2]){
            if (inbox(x-2,y-1)&& !dp[x-2][y-1][1]) qu.push(vector<int>{x-2,y-1,e[2],e[3]});
            if (inbox(x-2,y+1)&& !dp[x-2][y+1][1]) qu.push(vector<int>{x-2,y+1,e[2],e[3]});
            if (inbox(x-1,y-2)&& !dp[x-1][y-2][1]) qu.push(vector<int>{x-1,y-2,e[2],e[3]});
            if (inbox(x-1,y+2)&& !dp[x-1][y+2][1]) qu.push(vector<int>{x-1,y+2,e[2],e[3]});
            if (inbox(x+2,y-1)&& !dp[x+2][y-1][1]) qu.push(vector<int>{x+2,y-1,e[2],e[3]});
            if (inbox(x+2,y+1)&& !dp[x+2][y+1][1]) qu.push(vector<int>{x+2,y+1,e[2],e[3]});
            if (inbox(x+1,y-2)&& !dp[x+1][y-2][1]) qu.push(vector<int>{x+1,y-2,e[2],e[3]});
            if (inbox(x+1,y+2)&& !dp[x+1][y+2][1]) qu.push(vector<int>{x+1,y+2,e[2],e[3]});
        }else{
            if (inbox(x-1,y-1)&& !dp[x-1][y-1][0]) qu.push(vector<int>{x-1,y-1,e[2],e[3]});
            if (inbox(x-1,y+1)&& !dp[x-1][y+1][0]) qu.push(vector<int>{x-1,y+1,e[2],e[3]});
            if (inbox(x+1,y-1)&& !dp[x+1][y-1][0]) qu.push(vector<int>{x+1,y-1,e[2],e[3]});
            if (inbox(x+1,y+1)&& !dp[x+1][y+1][0]) qu.push(vector<int>{x+1,y+1,e[2],e[3]});
        }
        qu.pop();
    }
            
    cout << -1 << endl;
    return 0;
}
0