結果

問題 No.367 ナイトの転身
コンテスト
ユーザー nanophoto12
提出日時 2016-05-07 23:33:37
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 3,181 bytes
コンパイル時間 816 ms
コンパイル使用メモリ 96,076 KB
実行使用メモリ 6,528 KB
最終ジャッジ日時 2024-10-05 10:29:29
合計ジャッジ時間 2,118 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
using namespace std;

#define ll long long int
#define ti4 tuple<int,int,int,int>
#define pii pair<int,int>

int B[2][500][500];
int red[500][500];

int main()
{
    int H, W;
    cin >> H >> W;
    fill(&red[0][0], &red[0][0] + 500 * 500, 0);
    fill(&B[0][0][0], &B[0][0][0] + 2 * 500 * 500, 1e6);
    pii start;
    pii end;
    for(int i = 0;i < H;i++)
    {
        string s;
        cin >> s;
        for(int j = 0;j < W;j++)
        {
            if(s[j] == 'S')
            {
                start = make_pair(j, i);
            }
            else if(s[j] == 'G')
            {
                end = make_pair(j, i);
            }
            else if(s[j] == 'R')
            {
                red[j][i] = 1;
            }
        }
    }
    priority_queue<ti4, vector<ti4>, greater<ti4>> q;
    q.push(make_tuple(0, start.first, start.second, 0));
    B[0][start.second][start.first] = 0;
    while(!q.empty())
    {
        int count, x, y, board;
        tie(count, x, y, board) = q.top();
        //cout << count << "," << x << "," << y << "," << board << endl;
        q.pop();
        if(x == end.first && y == end.second)
        {
            cout << count << endl;
            return 0;
        }
        int nc = count + 1;
        if(board == 0)
        {
            pii shift[] = {make_pair(-1,-2),make_pair(-2,-1),make_pair(1,-2),make_pair(2,-1),
                make_pair(-1,2),make_pair(-2,1),make_pair(1,2),make_pair(2,1)};
            for(int i = 0;i < 8;i++)
            {
                int nx = x + shift[i].first;
                int ny = y + shift[i].second;
                if(nx >= 0 && nx < W && ny >= 0 && ny < H)
                {
                    if(B[board][ny][nx] <= nc)
                    {
                        continue;
                    }
                    B[board][ny][nx] = nc;
                    if(red[ny][nx])
                    {
                        q.push(make_tuple(nc, nx, ny, 1));
                    }
                    else
                    {
                        q.push(make_tuple(nc, nx, ny, 0));
                    }
                }
            }
        }
        else
        {
            pii shift[] = {make_pair(-1,-1),make_pair(1,-1),make_pair(-1,1),make_pair(1,1)};
            for(int i = 0;i < 4;i++)
            {
                int nx = x + shift[i].first;
                int ny = y + shift[i].second;
                if(nx >= 0 && nx < W && ny >= 0 && ny < H)
                {
                    if(B[board][ny][nx] <= nc)
                    {
                        continue;
                    }
                    B[board][ny][nx] = nc;
                    if(red[ny][nx])
                    {
                        q.push(make_tuple(nc, nx, ny, 0));
                    }
                    else
                    {
                        q.push(make_tuple(nc, nx, ny, 1));
                    }
                }
            }
            
        }
    }
    cout << -1 << endl;
    return 0;
}
0