靈犬尋寶

問題敘述：

正方形(左下角座標為(0,0)，右上角座標為(99,99))的格網上，有一隻靈犬要尋找一個寶物，格網上除了靈犬與寶物之外，還有一些障礙物。一般情況下，只要不超出格網的邊界，靈犬的每一步最多有8 個方向可供選擇，如圖一；



但是必須注意，只有在A 點沒有障礙物時才可以選擇方向1 或方向2，只有在B點沒有障礙物時才可以選擇方向3 或方向4，只有在C 點沒有障礙物時才可以選擇方向5 或方向6，只有在D 點沒有障礙物時才可以選擇方向7 或方向8。如果靈犬可以從出發的位置走到寶物的位置，其總共使用的步數，理論上應有一個最小值；但是靈犬也有可能無法走到寶物的位置。過程中，靈犬不可以
走到障礙物的位置上。



以圖二為例，有多達4 個障礙物介於靈犬與寶物之間，但是靈犬最快只要2步就可以到達寶物的位置。圖三是另一個例子，靈犬的位置靠近角落，雖然只有2 個障礙物，靈犬卻無法到達寶物的位置。請撰寫一個程式，若靈犬可以從最初位置走到寶物的位置時，請列印出其使用之最少步數；若靈犬無法到達寶物的位置，請列印出單字『impossible』。

輸入說明：

第一行為一個整數n，代表障礙物的個數，0 ≦ n ≦ 1000。接下來的n 行，每行表示一個障礙物的座標，其橫座標值與縱座標值間以一個空白隔開。再下來的一行，表示靈犬的最初位置，其橫座標值與縱座標值間以一個空白隔開。最後一行，代表寶物的位置，其橫座標值與縱座標值間以一個空白隔開。注意：輸入之障礙物、靈犬、寶物皆在不同位置。所有橫、縱座標值均為介於0(含)至99(含)之間的整數。

輸出說明：

依行走之規則，若靈犬可以從其位置走到寶物的位置時，請列印出其使用之最少步數；若靈犬無法到達寶物的位置，請列印出單字『impossible』。

輸入範例1：
4
3 6
4 5
5 4
6 3
3 3
7 5

輸出範例1：
2

輸入範例2：
2
1 1
0 2
0 1
4 3

輸出範例2：
impossible

====================================================
Note. 所求為最少步數，故不必記錄路徑，使用BFS一步步逼近寶物，也
　　　不會有走到重複點卻需要覆蓋的問題，且由於水平或垂直的移動皆
　　　為偶數的組合步，故每一步的上下左右都無法走到，頂多只會有棋
　　　盤的一半被走到。
====================================================

#include <stdio.h>
#include <stdlib.h>

#define BOARD_SIZE 100
#define MAX_QUEUE BOARD_SIZE*BOARD_SIZE/2

/* global variables */

int board[BOARD_SIZE+6][BOARD_SIZE+6];
/* the direction index of the dog's moving directions */
int dir_ver[8]={1,-1,-3,-3,-1,1,3,3};
int dir_hor[8]={3,3,1,-1,-3,-3,-1,1};
/* the direction index of the obstacles */
int dir_block_ver[4]={0,-1,0,1};
int dir_block_hor[4]={1,0,-1,0};

/* data structure of the queue */
typedef struct Position
{
　/* location */
　int x;
　int y;
　/* number of foot steps */
　int count;
}Position;

Position pos[MAX_QUEUE];

/* function prototype */

void initial(const int,const int,const int,const int [],const int []);
int find(const int,const int,const int,const int);

int main()
{
　/* read and open the input file named "H04dat.txt" */
　FILE *fp;
　fp=fopen("H04dat.txt","r");
　int i,ans,obstacle;

　/* set up the blocks */
　fscanf(fp,"%d",&obstacle);
　int x[obstacle],y[obstacle];
　for(i=0;i<obstacle;i++)
　　fscanf(fp,"%d%d",&x[i],&y[i]);

　/* set up the start and end points */
　int start_x,start_y,end_x,end_y;
　fscanf(fp,"%d%d",&start_x,&start_y);
　fscanf(fp,"%d%d",&end_x,&end_y);

　/* intialize the board */
　initial(start_x+3,start_y+3,obstacle,x,y);

　/* if the treasure and the dog is on the same location */
　if(start_x==end_x&&start_y==end_y)
　　printf("0\n");
　else
　　/* find the treasure */
　　if((ans=find(start_x+3,start_y+3,end_x+3,end_y+3))>0)
　　　printf("%d\n",ans);
　　else
　　　/* if the treasure and the obstacle is on the same location */
　　　printf("impossible\n");

　/* close the input file */
　fclose(fp);

　system("PAUSE");
　return 0;
}

/* initialize the board */
void initial(const int sx,const int sy,const int obstacle,const int x[],const int y[])
{
　int i,j;
　/* set the outside boundary to -1, others to 0 */
　for(i=0;i<BOARD_SIZE+6;i++)
　　for(j=0;j<BOARD_SIZE+6;j++)
　　　board[i][j]=(i>2&&i<BOARD_SIZE+3&&j>2&&j<BOARD_SIZE+3)?0:-1;

　/* put down the blocks */
　for(i=0;i<obstacle;i++)
　　board[y[i]+3][x[i]+3]=-1;

　/* because it's meaningless that move to the start point */
　board[sy][sx]=-1;

　/* initialize the queue */
　pos[0].x=sx;
　pos[0].y=sy;
　pos[0].count=0;
}

/* return the minimum steps if the dog can find the treasure, */
/* return 0 if false */
int find(const int sx,const int sy,const int ex,const int ey)
{
　int i,j,idx;

　/* the four directions of each foot step are unreachable */
　if((ex+sx+ey+sy)%2)
　　return 0;

　/* scan the whole queue */
　for(i=0,idx=1;i<idx;i++)
　{
　　/* if the dog has already found the treasure then return the steps */
　　/* use this condition may run more times "if(pos[i].y==ey&&pos[i].x==ex)" */
　　if(board[ey][ex]!=0)
　　　return board[ey][ex];

　　/* using BFS the find out the next eight directions */
　　for(j=0;j<8;j++)
　　　/* if the obstacle is not near the dos's present location */
　　　if(board[pos[i].y+dir_block_ver[j/2]][pos[i].x+dir_block_hor[j/2]]!=-1)
　　　　/* if any direction is reachable then PUSH into the queue */
　　　　if(!board[pos[i].y+dir_ver[j]][pos[i].x+dir_hor[j]])
　　　　{
　　　　　pos[idx].x=pos[i].x+dir_hor[j];
　　　　　pos[idx].y=pos[i].y+dir_ver[j];
　　　　　pos[idx++].count=pos[i].count+1;
　　　　　board[pos[i].y+dir_ver[j]][pos[i].x+dir_hor[j]]=pos[i].count+1;
　　　　}
　}
}