【題解】ZeroJudge b059: 4. 靈犬尋寶

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define ms(i) memset(i, 0, sizeof(i))
#define pii pair<int,int>
#define F first
#define S second

int g[105][105];
int dx[] = {-3, -3, -1, 1, 3, 3, 1, -1};
int dy[] = {1, -1, -3, -3, -1, 1, 3, 3};
int check[][2] = {{-1, 0}, {-1, 0}, {0, -1}, {0, -1}, {1, 0}, {1, 0}, {0, 1}, {0, 1}};
pii dst, now;
  
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, x, y, nx, ny;
    while (cin >> n){
        ms(g);
        for (int i=0; i<n; i++){
            cin >> x >> y;
            g[x][y] = -1;
        }
        cin >> x >> y;
        queue <pii> q;
        q.push({x, y});
        g[x][y] = 1;
        cin >> dst.F >> dst.S;
        bool canFind = false;
        while (!q.empty()){
            now = q.front();
            q.pop();
            x = now.F;
            y = now.S;
            for (int i=0; i<8; i++){
                nx = x + check[i][0];
                ny = y + check[i][1];
                if (nx < 0 || nx > 99 || ny < 0 || ny > 99 || g[nx][ny] == -1) continue;
                nx = x + dx[i];
                ny = y + dy[i];
                if (nx < 0 || nx > 99 || ny < 0 || ny > 99 || g[nx][ny] != 0) continue;
                q.push({nx, ny});
                g[nx][ny] = g[x][y] + 1;
                if (nx == dst.F && ny == dst.S){
                    canFind = true;
                    break;
                }
            }
        }
        if (canFind) cout << g[dst.F][dst.S] - 1 << '\n';
        else cout << "impossible\n";
    }
}

import sys
for line in sys.stdin:
    n = int(line)
    g = [[0 for j in range(100)] for i in range(100)]
    dx = [-3, -3, -1, 1, 3, 3, 1, -1]
    dy = [1, -1, -3, -3, -1, 1, 3, 3]
    check = [(-1, 0), (-1, 0), (0, -1), (0, -1), (1, 0), (1, 0), (0, 1), (0, 1)]
    
    for _ in range(n):
        x, y = map(int, sys.stdin.readline().split())
        g[x][y] = -1
        
    x, y = map(int, sys.stdin.readline().split())
    q = [(x, y)]
    g[x][y] = 1
    
    dst_x, dst_y = map(int, sys.stdin.readline().split())
    canFind = False
    while q:
        x, y = q.pop(0)
        for i in range(8):
            nx = x + check[i][0]
            ny = y + check[i][1]
            if nx < 0 or nx > 99 or ny < 0 or ny > 99 or g[nx][ny] == -1:
                continue
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx > 99 or ny < 0 or ny > 99 or g[nx][ny] != 0:
                continue
            q.append((nx, ny))
            g[nx][ny] = g[x][y] + 1
            if nx == dst_x and ny == dst_y:
                canFind = True
                break

    if canFind:
        print(g[dst_x][dst_y] - 1)
    else:
        print("impossible")