POJ -1753-Flip Game

5881 단어 game
http://poj.org/problem?id=1753
이 문 제 는 깊이 파고 들 었 지만 조작 방식 이 귀 찮 았 습 니 다. o (2 ^ 16) 그리고 읽 을 때% c 를 사용 해서 비극 적 이 었 습 니 다.
#include<cstdio>
#include<cstring>
#include<cstdlib>

int map[4][4];
int dx[] = { 1, -1, 0, 0};
int dy[] = { 0, 0, -1, 1};
int min = 100;

void init()
{
char a[10];
for( int i = 0; i < 4; i ++)
{
scanf( "%s", a);
for( int j = 0; j < 4; j ++)
{
if( a[j] == 'b') map[i][j] = 1;
else
map[i][j] = 0;
}
}
}

void Flip( int x, int y)
{
if( x < 0 || x > 3 || y < 0 || y > 3)
return;
map[x][y] = !map[x][y];
}

void turn( int pos)
{
int x = pos / 4;
int y = pos % 4;
Flip( x, y);
for( int i = 0; i < 4; i ++)
{
int nx = x + dx[i];
int ny = y + dy[i];
Flip( nx, ny);
}
}

bool check()
{
int t = 0;
for( int i = 0; i < 16; i ++)
t += map[i / 4][i % 4];
return t % 16 == 0 ? true : false;
}

void dfs( int pos, int step)
{
bool ok = check();
if( ok)
{
if (min > step)
min = step;
return;
}
if( pos >= 16) return;
dfs( pos + 1, step);
turn( pos); //
dfs( pos + 1, step + 1); // , 1
turn( pos); //
}

int main()
{
init();
dfs( 0, 0);
if( min > 16)
printf( "Impossible
");
else
printf( "%d
", min);
return 0;
}

좋은 웹페이지 즐겨찾기