Wikioi Problem 1004

gistfile1.c

/* Wikioi - Problem 1004. */
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define QUEUE_MAXSIZE	65535
#define	QUEUE_DELTASZ	65535
#define BOARD_SIZE			4

typedef long long llint;

typedef struct _status
{
	char board[BOARD_SIZE][BOARD_SIZE];
	int x[4],y[4];	/* 0-1 for now, 2-3 for pre. 2 to 0, 3 to 1. */
	llint nsteps;
	char player;	/* 'B' for black, 'W' for white. */
}status, *p_status;

void
stacpy(p_status dest, status src)
{
	int i = 0, j = 0;
	for(i = 0;i < BOARD_SIZE;++i)
		for(j = 0;j < BOARD_SIZE;++j)
		{
			dest->board[i][j] = src.board[i][j];
		}
	for(i = 0;i < 4;++i)
	{
			dest->x[i] = src.x[i];
			dest->y[i] = src.y[i];
	}
	dest->nsteps = src.nsteps;
	dest->player = src.player;
}

typedef struct _queue
{
	llint size;
	p_status data;
	int head, tail;
}queue, *p_queue;

void
initq(p_queue q)
{
	q->size = QUEUE_MAXSIZE + 1;
	q->data = (p_status)malloc(q->size * sizeof(status));
	q->head = q->tail = 0;
}

void
clear(p_queue q)
{
	q->head = q->tail = 0;
}

void
destory(p_queue q)
{
	free(q->data);
}

int
is_empty(queue q)
{
	return (q.head == q.tail);
}

int
is_full(queue q)
{
	return ( (q.tail+1)%(q.size) == q.head );
}

void
greatenq(p_queue q)
{
	int i = 0;
	llint nsize = q->size + QUEUE_DELTASZ;
	p_status ndata = (p_status)malloc(nsize * sizeof(status));
	
	for(i = q->head;i%(q->size) != q->tail;++i)
		ndata[i-q->head] = q->data[i%(q->size)];
	
	q->tail = i-q->head;
	q->head = 0;
	free(q->data);
	q->data = ndata;
	q->size = nsize;
}

void
enq(p_queue q, status s)
{
	if( is_full(*q) )
		greatenq(q);
	stacpy(&(q->data[q->tail]), s);
	q->tail = (q->tail+1)%(q->size);
}

void
deq(p_queue q, p_status s)
{
	if( is_empty(*q) )
		return ;
	stacpy(s, q->data[q->head]);
	q->head = (q->head+1)%(q->size);
}

int
check(status s)
{
	int isok = 1;
	int i = 0, j = 0;
	for(i = 0;i < 4;i++)
	{
		isok = 1;
		for(j = 1;j < 4;++j)
			if( s.board[i][j] != s.board[i][j-1] )
			{
				isok = 0;
				break;
			}
		if( isok )
			return 1;
	}
	for(j = 0;j < 4;++j)
	{
		isok = 1;
		for(i = 1;i < 4;++i)
			if( s.board[i][j] != s.board[i-1][j] )
			{
				isok = 0;
				break;
			}
		if( isok )
			return 1;
	}
	isok = 1;
	for(i = 1;i < 4;++i)
		if( s.board[i][i] != s.board[i-1][i-1] )
		{
			isok = 0;
			break;
		}
	if( isok )
		return 1;
	isok = 1;
	for(i = 1;i < 4;++i)
		if( s.board[i][3-i] != s.board[i-1][4-i] )
		{
			isok = 0;
			break;
		}
	if(isok)
		return 1;
	
	return 0;
}

int
main(void)
{
	int i = 0, j = 0, nw = 0;
	queue q;
	status initialb;
	int di[4] = {-1,0,1,0}, dj[4] = {0,-1,0,1};
	llint min = 1<<31-1;
	
	for(i = 0;i < 4;++i)
	{
		for(j = 0;j < 4;++j)
		{
			scanf("%c", &( initialb.board[i][j] ));
			if( 'O' == initialb.board[i][j] )
			{
				initialb.x[nw] = i;
				initialb.y[nw] = j;
				++nw;
			}
		}
		getchar();
	}
	
	/* bfs. */
	initq(&q);
	initialb.nsteps = 0;
	initialb.x[2] = initialb.x[3] = initialb.y[2] = initialb.y[3] = -1;
	initialb.player = 'B';
	enq(&q, initialb);
	initialb.player = 'W';
	enq(&q, initialb);
	while( 0 == is_empty(q) )
	{
		status cur, tmp;
		int o = 0, d = 0;
		int ti = 0, tj = 0;
		
		deq(&q, &cur);
		
		if( check(cur) )
		{
			if( cur.nsteps < min )
				min = cur.nsteps;
			if( cur.nsteps - min > 2 )
				break;
		}
		
		for(o = 0;o < 2;++o)
		{
			for(d = 0;d < 4;++d)
			{
				ti = cur.x[o] + di[d];
				tj = cur.y[o] + dj[d];
				
				if( ti < 0 || tj < 0 || ti > 3 || tj > 3 )	/* out of board. */
					continue;
				if( ti == cur.x[o+2] && tj == cur.y[o+2] )	/* it refers to going back. */
					continue;
				if( cur.board[ti][tj] != cur.player )	/* not on his turn. */
					continue;
				
				/* now enq it. */
				stacpy(&tmp, cur);
				tmp.board[tmp.x[o]][tmp.y[o]] = tmp.board[ti][tj];
				tmp.board[ti][tj] = 'O';
				tmp.x[o+2] = tmp.x[o];
				tmp.y[o+2] = tmp.y[o];
				tmp.x[o] = ti;
				tmp.y[o] = tj;
				++ (tmp.nsteps);
				tmp.player = ('B' == tmp.player)?('W'):('B');
				enq(&q, tmp);
			}
		}
	}
	
	printf("%lld\n", min);
	return 0;
}