結果
| 問題 |
No.3121 Prime Dance
|
| コンテスト | |
| ユーザー |
 hirayuu_yc
|
| 提出日時 | 2025-04-19 12:52:26 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,476 bytes |
| コンパイル時間 | 4,309 ms |
| コンパイル使用メモリ | 307,484 KB |
| 実行使用メモリ | 206,592 KB |
| 最終ジャッジ日時 | 2025-04-19 12:52:38 |
| 合計ジャッジ時間 | 12,003 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 19 WA * 2 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:179:18: warning: overflow in conversion from ‘long long int’ to ‘std::vector<int>::value_type’ {aka ‘int’} changes value from ‘1152921504606846976’ to ‘0’ [-Woverflow]
179 | px.push_back(INF);
| ^~~
main.cpp:180:18: warning: overflow in conversion from ‘long long int’ to ‘std::vector<int>::value_type’ {aka ‘int’} changes value from ‘1152921504606846976’ to ‘0’ [-Woverflow]
180 | py.push_back(INF);
| ^~~
ソースコード
/*
from collections import deque
from bisect import bisect_left
H,W=map(int,input().split())
sx,sy=map(int,input().split())
gx,gy=map(int,input().split())
S=["#"*(W+2) for i in range(H+2)]
for i in range(H):
S[i+1]="#"+input()+"#"
S=[list(s) for s in S]
S[sx][sy]="."
S[gx][gy]="."
H+=2
W+=2
num=[[0]*W for i in range(H)]
for i in range(1,H-1):
for j in range(1,W-1):
if S[i-1][j]=="." or S[i+1][j]==".":
num[i][j]^=1
if S[i][j-1]=="." or S[i][j+1]==".":
num[i][j]^=2
dist=[[[[1<<60]*4 for i in range(1600)] for i in range(W)] for i in range(H)]
dist[sx][sy][0][num[sx][sy]]=0
vert=deque()
vert.append((0,sx,sy,0,num[sx][sy]))
while vert:
d,x,y,r,b=vert.popleft()
if dist[x][y][r][b]!=d:
continue
if S[x+1][y]==".":
if dist[x+1][y][r][b|num[x+1][y]]>d+1:
dist[x+1][y][r][b|num[x+1][y]]=d+1
vert.append((d+1,x+1,y,r,b|num[x+1][y]))
if S[x-1][y]==".":
if dist[x-1][y][r][b|num[x-1][y]]>d:
dist[x-1][y][r][b|num[x-1][y]]=d
vert.appendleft((d,x-1,y,r,b|num[x-1][y]))
if S[x][y+1]==".":
if r!=1599 and dist[x][y+1][r+1][b|num[x][y+1]]>d:
dist[x][y+1][r+1][b|num[x][y+1]]=d
vert.appendleft((d,x,y+1,r+1,b|num[x][y+1]))
if S[x][y-1]==".":
if dist[x][y-1][r][b|num[x][y-1]]>d:
dist[x][y-1][r][b|num[x][y-1]]=d
vert.appendleft((d,x,y-1,r,b|num[x][y-1]))
swx=gx-sx
swy=gy-sy
X=30000
primes=[1]*X
primes[0]=0
primes[1]=0
for i in range(2,X):
if primes[i]==0:
continue
for j in range(i*2,X,i):
primes[j]=0
px=[]
py=[]
for i in range(X):
if 0<=i-swx<X and primes[i] and primes[i-swx]:
px.append(i)
for i in range(X):
if 0<=i-swy<X and primes[i] and primes[i-swy]:
py.append(i)
px.append(1<<60)
py.append(1<<60)
ans=1<<60
for i in range(1600):
ans=min(ans,(px[bisect_left(px,dist[gx][gy][i][3])]+py[bisect_left(py,i)])*2-swx-swy)
if ans>=(1<<60):
print(-1)
else:
print(ans)
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;
int main() {
int H, W;
cin >> H >> W;
int sx, sy, gx, gy;
cin >> sx >> sy >> gx >> gy;
vector<string> S(H + 2, string(W + 2, '#'));
for (int i = 0; i < H; ++i) {
string row;
cin >> row;
S[i + 1] = "#" + row + "#";
}
S[sx][sy] = '.';
S[gx][gy] = '.';
H += 2;
W += 2;
vector<vector<int>> num(H, vector<int>(W, 0));
for (int i = 1; i < H - 1; ++i) {
for (int j = 1; j < W - 1; ++j) {
if (S[i - 1][j] == '.' || S[i + 1][j] == '.') num[i][j] ^= 1;
if (S[i][j - 1] == '.' || S[i][j + 1] == '.') num[i][j] ^= 2;
}
}
vector<vector<vector<vector<ll>>>> dist(H,
vector<vector<vector<ll>>>(W,
vector<vector<ll>>(1600,
vector<ll>(4, INF))));
dist[sx][sy][0][num[sx][sy]] = 0;
deque<tuple<ll, int, int, int, int>> vert;
vert.emplace_back(0, sx, sy, 0, num[sx][sy]);
while (!vert.empty()) {
auto [d, x, y, r, b] = vert.front();
vert.pop_front();
if (dist[x][y][r][b] != d) continue;
if (S[x + 1][y] == '.') {
int nb = b | num[x + 1][y];
if (dist[x + 1][y][r][nb] > d + 1) {
dist[x + 1][y][r][nb] = d + 1;
vert.emplace_back(d + 1, x + 1, y, r, nb);
}
}
if (S[x - 1][y] == '.') {
int nb = b | num[x - 1][y];
if (dist[x - 1][y][r][nb] > d) {
dist[x - 1][y][r][nb] = d;
vert.emplace_front(d, x - 1, y, r, nb);
}
}
if (S[x][y + 1] == '.') {
if (r != 1599) {
int nb = b | num[x][y + 1];
if (dist[x][y + 1][r + 1][nb] > d) {
dist[x][y + 1][r + 1][nb] = d;
vert.emplace_front(d, x, y + 1, r + 1, nb);
}
}
}
if (S[x][y - 1] == '.') {
int nb = b | num[x][y - 1];
if (dist[x][y - 1][r][nb] > d) {
dist[x][y - 1][r][nb] = d;
vert.emplace_front(d, x, y - 1, r, nb);
}
}
}
int swx = gx - sx;
int swy = gy - sy;
const int X = 30000;
vector<bool> primes(X, true);
primes[0] = primes[1] = false;
for (int i = 2; i < X; ++i) {
if (!primes[i]) continue;
for (int j = i * 2; j < X; j += i) {
primes[j] = false;
}
}
vector<int> px, py;
for (int i = 0; i < X; ++i) {
if (i - swx >= 0 && i - swx < X && primes[i] && primes[i - swx]) {
px.push_back(i);
}
}
for (int i = 0; i < X; ++i) {
if (i - swy >= 0 && i - swy < X && primes[i] && primes[i - swy]) {
py.push_back(i);
}
}
px.push_back(INF);
py.push_back(INF);
ll ans = INF;
for (int i = 0; i < 1600; ++i) {
ll d = dist[gx][gy][i][3];
int idx_px = lower_bound(px.begin(), px.end(), d) - px.begin();
int idx_py = lower_bound(py.begin(), py.end(), i) - py.begin();
if (idx_px < px.size() && idx_py < py.size()) {
ll cand = (ll(px[idx_px]) + ll(py[idx_py])) * 2 - swx - swy;
ans = min(ans, cand);
}
}
if (ans >= INF) {
cout << -1 << endl;
} else {
cout << ans << endl;
}
return 0;
}