#include using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int H,W; int Sx,Sy,Gx,Gy; cin >> H >> W; cin >> Sx >> Sy >> Gx >> Gy; vector C(H); for(int i=0;i> C[i]; // 1) BFS で最短距離 L0 を求める vector> dist(H, vector(W, -1)); deque> dq; dist[Sx-1][Sy-1] = 0; dq.emplace_back(Sx-1, Sy-1); int dx4[4] = {1,-1,0,0}, dy4[4] = {0,0,1,-1}; while(!dq.empty()){ auto [x,y] = dq.front(); dq.pop_front(); 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; dq.emplace_back(nx,ny); } } int L0 = dist[Gx-1][Gy-1]; if(L0<0){ cout << -1; return 0; } // 成分内到達マーク vector> vis(H, vector(W,false)); for(int i=0;i=0) vis[i][j]=true; // 2) Δx,Δy の計算 int dx = Gx - Sx; int dy = Gy - Sy; // 3) 隣接セルの有無 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); // (Δx)方向のペア vector sumV; for(int p2: primes){ int p1 = p2 + dx; if(p1>=2 && p1<=Np && isP[p1]){ sumV.push_back(p1 + p2); } } // (Δy)方向 vector sumH; for(int p2: primes){ int p1 = p2 + dy; if(p1>=2 && p1<=Np && isP[p1]){ sumH.push_back(p1 + p2); } } if(sumV.empty() || sumH.empty()){ cout<<-1; return 0; } sort(sumV.begin(), sumV.end()); sort(sumH.begin(), sumH.end()); // ループ不可方向はベース1つに制限 if(!adjV) sumV.resize(1); if(!adjH) sumH.resize(1); // 5) 最小合計和 >= L0 を二分探索で int ans = INT_MAX; for(int vx: sumV){ int need = L0 - vx; auto it = lower_bound(sumH.begin(), sumH.end(), need); if(it!=sumH.end()){ ans = min(ans, vx + *it); } } if(ans==INT_MAX) ans = -1; cout << ans; return 0; }