結果

問題 No.3121 Prime Dance
コンテスト
ユーザー 入野拳樹
提出日時 2025-04-20 16:44:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,792 bytes
コンパイル時間 2,462 ms
コンパイル使用メモリ 210,504 KB
実行使用メモリ 144,928 KB
最終ジャッジ日時 2025-04-20 16:44:26
合計ジャッジ時間 9,657 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 8 WA * 2 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

const int MAX = 40;
const int INF = 1e9;

int H, W;
int Sx, Sy, Gx, Gy;
char grid[MAX][MAX];

struct State {
    int x, y;
    int a, b, c, d;
};

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

int main() {
	
	vector<bool>sosu(20001,true);
	sosu[0] = false;
	sosu[1] = false;
	for(int i = 2;i<450;i++){
		if(sosu[i] != true)continue;
		else{
			long long j = 2;
			while(j*i < 20001){
				sosu[j*i] = false;
				j++;
			}
		}
	}
	
    cin >> H >> W;
    cin >> Sx >> Sy;
    cin >> Gx >> Gy;
    Sx--; Sy--; Gx--; Gy--;

    for (int i = 0; i < H; ++i) {
        cin >> grid[i];
    }

    queue<State> q;
    set<tuple<int, int, int, int, int, int>> visited;

    q.push({Sx, Sy, 0, 0, 0, 0});
    visited.insert({Sx, Sy, 0, 0, 0, 0});

    int ans = INF;

    while (!q.empty()) {
        State s = q.front(); q.pop();

        if (s.x == Gx && s.y == Gy) {
            if (sosu[s.a] && sosu[s.b] && sosu[s.c] && sosu[s.d]) {
                ans = min(ans, s.a + s.b + s.c + s.d);
            }
        }

        for (int dir = 0; dir < 4; ++dir) {
            int nx = s.x + dx[dir];
            int ny = s.y + dy[dir];

            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (grid[nx][ny] == '#') continue;

            int na = s.a + (dir == 0);
            int nb = s.b + (dir == 1);
            int nc = s.c + (dir == 2);
            int nd = s.d + (dir == 3);

            if (na > 150 || nb > 150 || nc > 150 || nd > 150) continue;

            auto state = make_tuple(nx, ny, na, nb, nc, nd);
            if (visited.count(state)) continue;
            visited.insert(state);
            q.push({nx, ny, na, nb, nc, nd});
        }
    }

    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}
0