#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(int i=0;i> C[i]; // 1) BFS で到達可能性チェック vector dist(H, vector(W, -1)); queue> q; dist[Sx-1][Sy-1] = 0; q.emplace(Sx-1, Sy-1); 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]=='#') continue; if(dist[nx][ny]==-1){ dist[nx][ny] = dist[x][y] + 1; q.emplace(nx, ny); } } } if(dist[Gx-1][Gy-1] == -1){ cout << -1; return 0; } // 2) 素数列挙(上限は十分余裕を持って200まで) const int LIM = 200; vector is_prime(LIM+1, true); is_prime[0]=is_prime[1]=false; for(int i=2;i*i<=LIM;i++) if(is_prime[i]){ for(int j=i*i;j<=LIM;j+=i) is_prime[j]=false; } vector primes; for(int i=2;i<=LIM;i++) if(is_prime[i]) primes.push_back(i); int dx = abs(Gx - Sx); int dy = abs(Gy - Sy); // 3) (A,B) で A-B = dx を満たすものの最小 A+B ll bestV = LLONG_MAX; for(int p: primes) for(int q: primes){ if(p - q == dx){ bestV = min(bestV, ll(p) + ll(q)); } } // 4) (C,D) で C-D = dy を満たすものの最小 C+D ll bestH = LLONG_MAX; for(int p: primes) for(int q: primes){ if(p - q == dy){ bestH = min(bestH, ll(p) + ll(q)); } } if(bestV==LLONG_MAX || bestH==LLONG_MAX){ cout << -1; } else { cout << (bestV + bestH); } return 0; }