BOJ 5022

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

#define MAXN 101
#define INF 987654321

int path[MAXN*MAXN];

pair<int,int> coord[4];
bool visited[MAXN][MAXN];
int N,M;

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int ans = INF;
queue<pair<int,int> > q;
int bfs(pair<int,int> A, pair<int,int> B, pair<int,int> C, pair<int,int> D){
    q.push(A);
    visited[A.first][A.second] = true;
    int cnt = 0;
    while (!q.empty()){
        int q_size = q.size();
        while (q_size--){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            if (x == B.first && y == B.second) return cnt;
            for (int k =0 ;k< 4; k++){
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (nx < 0 || ny < 0 || nx>N || ny>M) continue;
                if (nx == C.first && ny == C.second) continue;
                if (nx == D.first && ny == D.second) continue;
                if (visited[nx][ny]) continue;
                visited[nx][ny] = true;
                path[nx*(M+1)+ny] = x*(M+1)+y;
                q.push({nx,ny});
            }
        }
        cnt++;
    }
    return INF;
}

void Init(){
    memset(path,-1,sizeof(path));
    memset(visited,false,sizeof(visited));
    while (!q.empty()) q.pop();
}
void check_path(pair<int,int> coord){
    memset(visited,false,sizeof(visited));
    while (!q.empty()) q.pop();
    int x = coord.first;
    int y = coord.second;
    int target = x*(M+1)+y;
    while (path[target]!= -1){
        visited[target/(M+1)][target%(M+1)] = true;
        target = path[target];
    }
    visited[target/(M+1)][target%(M+1)] = true;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(path,-1,sizeof(path));
    cin >> M >> N;
    for (int i = 0;i < 4;i++){
        cin >> coord[i].second >> coord[i].first;
    }
    int sum1 = bfs(coord[0],coord[1],coord[2],coord[3]);
    check_path(coord[1]);
    int sum2 = bfs(coord[2],coord[3],coord[0],coord[1]);
    if (max(sum1,sum2)!= INF) ans = min(ans,sum1+sum2);
    Init();
    sum1 = bfs(coord[2],coord[3],coord[0],coord[1]);
    check_path(coord[3]);
    sum2 = bfs(coord[0],coord[1],coord[2],coord[3]);
    if (max(sum1,sum2)!= INF) ans = min(ans,sum1+sum2);

    if (ans ==INF) cout <<"IMPOSSIBLE\n";
    else cout << ans <<"\n";
    return 0;
}