poj 1753 Flip Game http://poj.org/problem?id=1753

poj 1753

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

#define MAXN 65536

int DD[5][2] = {{0, 0}, {0, 1}, {0, -1}, {-1, 0}, {1, 0}};

struct _queue_struct
{
  int x, step;
};

typedef struct _queue_struct queue_struct;
queue_struct queue[MAXN];

int queue_head, queue_tail;
short flag[MAXN];

int
flip(int x, int y, int source)
{
	x = 3 - x;
	y = 3 - y;
	int tmp = y * 4 + x;
	return source ^ (1 << tmp);
}

void
initial_queue(int s)
{
	for (int i = 0; i < MAXN; ++i)
	{
		queue[i].step = 0;
		queue[i].x = -1;
		flag[i] = 0;
	}
    queue_head = queue_tail = 0;
	queue[0].x = s;
	queue[0].step = 0;
	flag[s] = 1;
}

int
checkLegal(int x, int y)
{
	return (x >= 0) && (x < 4) && (y >= 0) && (y < 4);
}

int main()
{
	int i, j;
	int s = 0; //all white
	for (i = 0; i < 4; i++)
		for (j = 0; j < 4; j++)
		{
			char ch;
			scanf("%c", &ch);
            while (ch == '\n')
            {
                scanf("%c", &ch);
            }
            
			if (ch == 'b')
				s = flip(j, i, s);
		}
	
    if (s == 65535 || s == 0)
    {
        printf("0\n");
        return 0;
    }
	initial_queue(s);
	    
	while (queue_tail >= queue_head)
	{
		queue_struct v = queue[queue_head];
        
		for (i = 0; i < 16; ++i)
		{
			int tmp = v.x;
			for (j = 0; j < 5; ++j)
			{
				int x = i % 4 + DD[j][0], y = i / 4 + DD[j][1];
                
				if (checkLegal(x, y))
					tmp = flip(x, y, tmp);
			}
			
			if (!flag[tmp])
			{
				if ((tmp == 0) || (tmp == MAXN-1))
				{
					printf("%d\n", v.step + 1);
					exit(0);
				}
                flag[tmp] = 1;
                queue_tail++;
                queue[queue_tail].step = v.step + 1;
                queue[queue_tail].x = tmp;
			}
		}
        
		queue_head ++;
	}
    
	printf("Impossible\n");
	return 0;
}