#include using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int H, W; int Sx, Sy, Gx, Gy; cin >> H >> W; cin >> Sx >> Sy >> Gx >> Gy; vector C(H); for(int i = 0; i < H; i++) cin >> C[i]; // 1) 最短距離 L0 を BFS で vector> dist(H, vector(W, -1)); queue> q; dist[Sx-1][Sy-1] = 0; q.emplace(Sx-1, Sy-1); const int dx4[4] = {1,-1,0,0}, dy4[4] = {0,0,1,-1}; while(!q.empty()){ auto [x,y] = q.front(); q.pop(); for(int d = 0; d < 4; d++){ int nx = x + dx4[d], ny = y + dy4[d]; if(nx<0||nx>=H||ny<0||ny>=W) continue; if(C[nx][ny]=='#' || dist[nx][ny]!=-1) continue; dist[nx][ny] = dist[x][y] + 1; q.emplace(nx, ny); } } int L0 = dist[Gx-1][Gy-1]; if(L0 < 0){ cout << -1 << "\n"; return 0; } // 2) 到達可能成分マーク vector> vis(H, vector(W,false)); for(int i=0;i=0) vis[i][j]=true; // 3) Δx,Δy の絶対値 dv,dh int dx = Gx - Sx, dy = Gy - Sy; int dv = abs(dx), dh = abs(dy); // 4) 成分内に縦・横の隣接があるか bool adjV = false, adjH = false; for(int i=0;i isP(Np+1, true); isP[0]=isP[1]=false; for(int i=2;i*i<=Np;i++) if(isP[i]) for(int j=i*i;j<=Np;j+=i) isP[j]=false; vector primes; for(int i=2;i<=Np;i++) if(isP[i]) primes.push_back(i); // 6) 縦方向ペア (差 = dv) vector sumV; for(int p : primes){ int q = p + dv; // ここを dx ではなく dv で if(q <= Np && isP[q]) sumV.push_back(p + q); } // 横方向ペア (差 = dh) vector sumH; for(int p : primes){ int q = p + dh; // ここも dh if(q <= Np && isP[q]) sumH.push_back(p + q); } if(sumV.empty() || sumH.empty()){ cout << -1 << "\n"; return 0; } sort(sumV.begin(), sumV.end()); sort(sumH.begin(), sumH.end()); // 7) 二分探索で最小合計 >= L0 int ans = INT_MAX; for(int v : sumV){ int need = L0 - v; auto it = lower_bound(sumH.begin(), sumH.end(), need); if(it != sumH.end()) ans = min(ans, v + *it); } if(ans == INT_MAX) ans = -1; cout << ans << "\n"; return 0; }