Skip to content

Instantly share code, notes, and snippets.

@rpplusplus
Created September 3, 2013 18:42
Show Gist options
  • Save rpplusplus/6427898 to your computer and use it in GitHub Desktop.
Save rpplusplus/6427898 to your computer and use it in GitHub Desktop.
poj 1753 Flip Game http://poj.org/problem?id=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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment