#include <iostream>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <queue>using namespace std;#define maxn 80struct Node{ int x, y, turn, d;};bool map[maxn][maxn];int vis[maxn][maxn];int m, n;int x1, y1, x2, y2;int dir[4][2] ={{ 1, 0 },{ 0, 1 },{ -1, 0 },{ 0, -1 } };bool operator <(const Node &a, const Node &b){ return a.turn > b.turn;}void input(){ getchar(); n++; m++; memset(map, 0, sizeof(map)); for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { char ch = getchar(); if (ch == 'X') map[i][j] = true; } getchar(); }}bool ok(Node &a){ if (a.x < 0 || a.y < 0 || a.x > n || a.y > m) return false; if (map[a.x][a.y]) return false; if (vis[a.x][a.y] == -1) return true; return vis[a.x][a.y] >= a.turn;}void bfs(int t){ priority_queue<Node> q; Node a; memset(vis, -1, sizeof(vis)); for (int i = 0; i < 4; i++) { a.x = x1; a.y = y1; a.turn = 0; a.d = i; q.push(a); } vis[x1][y1] = true; bool tf = map[x2][y2]; map[x2][y2] = false; while (!q.empty()) { a = q.top(); q.pop(); if (a.x == x2 && a.y == y2) { printf("Pair %d: %d segments.n", t, a.turn + 1); map[x2][y2] = tf; return; } for (int i = 0; i < 4; i++) { Node b; b.x = a.x + dir[i][0]; b.y = a.y + dir[i][1]; b.turn = a.turn; if (a.d != i) b.turn++; b.d = i; if (ok(b)) { q.push(b); vis[b.x][b.y] = b.turn; } } } printf("Pair %d: impossible.n", t); map[x2][y2] = tf;}int main(){ int t = 0; while (scanf("%d%d", &m, &n), n | m) { t++; printf("Board #%d:n", t); input(); int i = 0; while (scanf("%d%d%d%d", &y1, &x1, &y2, &x2), x1 | y1 | x2 | y2) bfs(++i); putchar('n'); } return 0;}
