08/03/06 21:50:12
>>550 の修正版 （完成した状態の定義は board_t board={{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,SPACE}}; とする）
#define HEIGHT 4
#define WIDTH 4
#define BOARD_SIZE ((HEIGHT)*(WIDTH))
#define SPACE ((BOARD_SIZE)-1)
typedef struct tag_board_t{ int num[BOARD_SIZE]; }board_t;
int swap(int *a, int *b){
int c; c=*a; *a=*b; *b=c;
return (*a!=SPACE && *b!=SPACE); // 空白との交換はカウントしない
}
int sign(int a){ return (a>0)?1:(a<0)?-1:0; } // 数値の符号を返すだけ
int is_solvable(board_t *board){
int check_pos, swap_pos, target_pos, swap_count=0;
int diff_x, diff_y;
board_t work;
work=*board;
for(check_pos=0;check_pos<WIDTH*HEIGHT;check_pos++){
for(target_pos=0;work.num[target_pos]!=check_pos;target_pos++);
while(work.num[check_pos]!=check_pos){
diff_x = (check_pos%WIDTH) - (target_pos%WIDTH);
diff_y = (check_pos/WIDTH) - (target_pos/WIDTH);
if(diff_x) swap_pos=target_pos + sign(diff_x);
else swap_pos=target_pos + sign(diff_y)*WIDTH;
swap_count+=swap(&work.num[target_pos], &work.num[swap_pos]);
target_pos=swap_pos;
}
}
return (swap_count%2==0);
}