靈犬尋寶

問題敘述：

正方形(左下角座標為(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;
　　　　}
　}
}

六芒星棋遊戲：先還是後比較有利？

問題敘述：
在一個稱為『六芒星』的星球上，流行著一種『六芒星棋』的遊戲。這種遊戲是由兩個人來比賽，道具是一個棋盤（如圖一）和13 個鐵圈。遊戲的起始狀態是由兩人互相協調或隨機決定，使用m 個（1 ≦ m ≦ 13）鐵圈在棋盤上圈住m個數字。接下來雙方輪流移除棋盤上的鐵圈，每人每次只能移除1個鐵圈或2個相鄰的鐵圈（有直線直接相連的位置視為相鄰），被迫移除最後一個鐵圈的人算輸。

其實如果仔細思考，可以證明不管起始狀態如何，遊戲中先移除鐵圈的人（先手）與其對手（後手）中必定恰有一人，只要他每次都用對自己最有利的方法來移除鐵圈，最後一定百分之百得勝。

以起始狀態如圖二為例，因為所有鐵圈均不相鄰，故一次只能移除一個鐵圈，先手不管移除哪一個圈，後手只要再移除一個圈，就可以逼迫先手移除最後一個圈，因此後手有百分之百得勝的把握，我們說成『圖二的起始狀態是後手有利』。若起始狀態如圖三就不同了，如果先手懂得先移除相鄰的兩個鐵圈（如2^7 與2^10），就可以迫使後手去移除最後一個圈，因此先手就有百分之百得勝的把握，我們說成『圖三的起始狀態是先手有利』。每一種起始狀態，我們用一個整數來表示它，這個整數就是在該起始狀態中所有被鐵圈圈住的數字總和。例如圖二的起始狀態可以用2^3+2^5+2^11=2088 表示，圖三則可用2^7+2^9+2^10=1664 來表示。

請你寫一個程式來判斷在不同的起始狀態下，到底是先手還是後手有利。

　

解法：
使用 Dynamic Programing，大問題由小問題所組成，大的數字由小的數字組成，故判斷 X 為先手或後手可用 X 的上一層來判斷，若 X 拿走一個鐵圈或拿走兩個鐵圈的狀況都是後手有利，則對 X 本身來說即是先手有利；若都是先手有利，對 X 本身來說則會是後手有利；若前一步有先手後手都有利的情況，則在不會選擇故意輸的條件下，必定是選先手有利。

　

Note：

１. 跳脫出圖形的限制，跟圖形沒有關係。

２. 建一 table，存放各種數字組合所對應的有利選擇，從小到大往後填滿。

３. 預設 table[0] 為先手有利。

//----- user definition -----
#define FIRST 1
#define SECOND 0
#define MAX_NUM 8192-1 //2^13-1
#define BOARD_NUM 13
#define NEIGH_NUM 6

//----- global variables -----
/* a table that records the output and initilize first element to 1 */
int table[MAX_NUM]={1};
int component[BOARD_NUM]; /* bit(board) number */

/* neighbors of each node */
int neighbor[BOARD_NUM][NEIGH_NUM+1]={{2,3,-1,-1,-1,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{2,5,-1,-1,-1,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{0,1,3,5,6,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{0,2,4,6,7,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{3,7,-1,-1,-1,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{1,2,6,8,9,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{2,3,5,7,9,10,-1},
　　　　　　　　　　　　　　　　　　　　　　{3,4,6,10,11,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{5,9,-1,-1,-1,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{5,6,8,10,12,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{6,7,9,11,12,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{7,10,-1,-1,-1,-1,-1},
　　　　　　　　　　　　　　　　　　　　　　{9,10,-1,-1,-1,-1,-1}};

//----- function prototype -----
int find(int,int); /* return which order is better */
void set_compo(int); /* set up the components of the sum */
/* extract one component of sum,
　 if equals 0 then return 1, otherwise return 0 */
int extract(int);

//----- functions -----
/* return which order is better at sum2 */
int find(int sum)
{
　int tmp_sum;

　/* find the output of sum step by step */
　for(tmp_sum=1;tmp_sum<=sum;tmp_sum++)
　{
　　/* set up the components of sum */
　　set_compo(tmp_sum);

　　/* find the output of each tmp_sum */
　　table[tmp_sum]=extract(tmp_sum);
　}
　/* return the result output */
　return table[sum];
}

/* store 2^idx if the index is one of the sum's component, otherwise stores 0 */
void set_compo(int sum)
{
　int i,mask=1;
　for(i=0;i<BOARD_NUM;i++,mask*=2)
　　component[i]=((mask&sum)==mask)?mask:0;
}

/* return FIRST if table[] is 0 */
/* otherwise return SECOND */
int extract(int sum)
{
　int i,j;
　/* scan all the component array */
　for(i=0;i<BOARD_NUM;i++)
　　/* if there is a nonzero in component */
　　if(component[i]!=0)
　　{
　　　/* test by extracting one value */
　　　if(!table[sum-component[i]])　return FIRST;

　　　/* scan this node's neighbor whether they are combined or not */
　　　for(j=0;neighbor[i][j]!=-1;j++)
　　　　/* if it is then test by extracting two values */
　　　　if(component[neighbor[i][j]]!=0)
　　　　　if(!table[sum-component[i]-component[neighbor[i][j]]])
　　　　　　return FIRST;
　　}
　/* if there's no 0s in table[] then SECOND is better */
　return SECOND;
}

Minimum and Maximum

// Find the maximum and minimum. Using non-recursive programming.
// Input file：void
// Output：Stdout (show on monitor)

int Minimum(char A[],int size)
{
　int min=A[0];
　int i;
　for(i=1;i>A[i];i++)
　　min=A[i];
　return min;
}

int Maximum(char A[],int size)
{
　int max=A[0];
　int i;
　for(i=1;i>A[i];i++)
　　max=A[i];
　return max;
}

Randomized-Select to find the ith smallest element

// Find the ith smallest element of the array A[p..r]. Using non-recursive programming.
// Input file：void
// Output：Stdout (show on monitor)

int Randomized_Select(char A[],int p,int r,int i)
{
　if(p==r)
　　return A[p];
　int q=Randomized_Partition(A,p,r);
　int k=q-p+1;
　if(i==k) // the pivot is the answer
　　return A[q];
　else if(ii-k);
}

// Using randomized method to find the KEY
int Randomized_Partition(char A[],int p,int r)
{
　int i=rand()%(r-p+1)+p;
　Swap(A,r,i);
　return Partition(A,p,r);
}

// Comparision and divide (1.> KEY 2.<= KEY)
int Partition(char A[],int p,int r)
{
　int x=A[r];
　int i=p-1;
　int j;
　for(j=p;j<=r-1;j++)
　　if(A[j]<=x)
　　　Swap(A,++i,j);
　Swap(A,i+1,r);
　return i+1;
}

// Exchange two elements of the data
void Swap(char A[],int i,int j)
{
　int temp=A[i];
　A[i]=A[j];
　A[j]=temp;
　return;
}