POJ 2965 The Pilots Brothers'refrigerator列挙

タイトル:http://poj.org/problem?id=2965
    1753と同様に4*4の碁盤でもあり、スイッチロックによって碁盤上のすべてのロックがOPENとなり、1つのロックを開くと行と列のロックの状態が同時に変更されます.分析:
    (1)同様に,各格子の鍵は1回だけ開くだけで十分である.2回開くと開かないに等しいからである.
    (2)碁盤の状態は開錠の順序とは関係なく,開錠の個数と位置のみに関係する.
    1つの鍵が開かないことを0-1で表すと,碁盤格子を求める01シーケンスに相当し,合計2^16の可能性があるため,列挙法を用いることができる.方法は1753と似ています(前のブログを参照).しかし、スイッチロックの位置を記録するためにpathを追加しました.コードは次のとおりです.

#include <stdio.h>

#define  ONLINE

void online()
{
#ifdef  ONLINE
#else
	freopen("2965.in", "r", stdin);
	freopen("2965.out", "w", stdout);
#endif
}

int map = 0;
const int END = 0X0000;
const int SIZE = 16;
const int state[SIZE] = {
	0xF888, 0xF444, 0xF222, 0xF111,
	0x8F88, 0x4F44, 0x2F22, 0x1F11,
	0x88F8, 0x44F4, 0x22F2, 0x11F1,
	0x888F, 0x444F, 0x222F, 0x111F
};
int result = 17;

int path=0;//      

void read()
{
	char c;
	for (int i=0; i < SIZE; i++)
	{
		c = getchar();

		if (c == '+')
		{
			map = map << 1;
			map = map ^ 1;
		}//end if
		else if (c == '-')
		{
			map = map << 1;
		}
		else{
			i --;
		}//end else
	}//end for
}

void search(int idx, int step, int p)
{
	if (step >= result)
	{
		return;
	}
	if (idx >= SIZE)
	{
		if (map == END && step < result)
		{
			result = step;
			path = p;
		}//end if
		return;
	}

	p = p << 1;
	p = p^1;
	map = map ^ state[idx];
	search(idx+1, step +1, p);
	map = map^state[idx];
	p = p >> 1;

	p = p << 1;
	search(idx+1, step, p);
	p = p >>1;
}

void print()
{
	printf("%d
", result);
	
	//    
	int bit = 15;
	for (int i=1; i <=4; i ++)
	{
		for (int j=1; j <= 4; j ++)
		{
			if ((path >> bit)&1 == 1)
			{
				printf("%d %d
", i, j);
			}// end if
			bit --;
		}//end for 
	}//end for
}


int main()
{
	online();
	read();
	search(0, 0, 0);
	print();
	return 0;
}

    実行結果は次のとおりです.
2965
Accepted
160K
63MS
C++
1430B
2011-07-29 22:17:01