#include using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int H, W, Sx, Sy, Gx, Gy; cin >> H >> W >> Sx >> Sy >> Gx >> Gy; vector C(H); for (auto &s : C) cin >> s; auto in = [&](int x,int y){ return 0<=x && x> dist(H, vector(W,-1)); queue> q; dist[Sx-1][Sy-1]=0; q.emplace(Sx-1,Sy-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(!in(nx,ny) || 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==-1){ cout<<-1<<"\n"; return 0; } /* 2) 成分内に縦/横エッジがあるか */ bool adjV=false, adjH=false; for(int i=0;i isP(PMAX+1,1); isP[0]=isP[1]=0; for(int i=2;i*i<=PMAX;i++) if(isP[i]) for(int j=i*i;j<=PMAX;j+=i) isP[j]=0; vector primes; primes.reserve(PMAX/10); for(int i=2;i<=PMAX;i++) if(isP[i]) primes.push_back(i); auto prime = [&](int x){ return x>1 && x<=PMAX && isP[x]; }; /* 4) 縦/横それぞれ「条件を満たす2素数の和」を列挙 */ vector sumV, sumH; if(dx>=0){ for(int A:primes){ int B=A-dx; if(B>0 && prime(B)) sumV.push_back(A+B); } }else{ for(int B:primes){ int A=B-dx; if(A>0 && prime(A)) sumV.push_back(A+B); } } if(dy>=0){ for(int Cc:primes){ int D=Cc-dy; if(D>0 && prime(D)) sumH.push_back(Cc+D); } }else{ for(int D:primes){ int Cc=D-dy; if(Cc>0 && prime(Cc)) sumH.push_back(Cc+D); } } if(sumV.empty() || sumH.empty()){ cout<<-1<<"\n"; return 0; } /* ループが挿入できない方向は最小値だけで十分 */ if(!adjV) sumV = { *min_element(sumV.begin(), sumV.end()) }; if(!adjH) sumH = { *min_element(sumH.begin(), sumH.end()) }; sort(sumV.begin(), sumV.end()); sort(sumH.begin(), sumH.end()); /* 5) v+h ≥ L0 を満たす最小値を二分探索で求める */ int ans = INT_MAX; for(int v : sumV){ int need = L0 - v; auto it = lower_bound(sumH.begin(), sumH.end(), max(need,0)); if(it!=sumH.end()) ans = min(ans, v + *it); } if(ans==INT_MAX) ans = -1; cout << ans << '\n'; return 0; }