POJ-2811:消灯問題(ボタンの問題、列挙)

POJ-2811:消灯の問題
説明
各行に6つのボタン、合計5行のボタンからなるマトリクスがあります.各ボタンの位置にランプがあります.1つのボタンを押すと、そのボタンと周囲の位置(上、下、左、右)のランプが1回変わります.すなわち、ランプが点灯していた場合、消灯する.もともと明かりが消えていたら、点灯されます.マトリクス角のボタンで3つのランプの状態を変更します.マトリクスエッジのボタンで4つのランプの状態を変更します.他のボタンは5つのランプの状態を変更します.
上図では、左マトリクスにXマークのボタン表示が押され、右マトリクスにランプ状態の変化が表示されます.マトリクス内の各ランプに初期状態を設定します.ボタンを押して、どれも消えるまで待ってください.1つのランプに隣接する複数のボタンが押されると、1つの操作が別の操作の結果を相殺します.下図では、2行目3、5列目のボタンが押されているので、2行目、4列目のランプの状態は変わりません.どのボタンを押す必要があるか、すべてのランプが消灯するようにプログラムを書いてください.上記のルールによれば,1)2回目に同じボタンを押すと,1回目の押したときの結果が相殺されることが分かる.そのため、ボタンごとに最大1回押すだけです.2)各ボタンが押される順番は最終的な結果に影響しない;3)1行目に点灯しているランプごとに、2行目に対応するボタンを押すと、1行目のランプを全て消灯できます.このように繰り返すと、1、2、3、4行目の全てのランプを消すことができます.同様に、1、2、3、4、5列目のボタンを押すと、前の5列のランプを消すことができます.
入力
最初の行は、解決すべきケース数を示す正の整数Nである.各ケースは5行で構成され、各行には6つの数字が含まれています.これらの数字は0または1のスペースで区切られています.0はランプの初期状態が消灯していることを示し、1はランプの初期状態が点灯していることを示している.
しゅつりょく
次に、この例の入力フォーマットに従って5行を出力し、そのうちの1は対応するボタンを押す必要があることを示し、0は対応するボタンを押す必要がないことを示す.各数字はスペースで区切られています.
サンプル入力
0 1 1 0 1 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 1 1 0 0
サンプル出力
1 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0

##   ：

                   。     
puzzle[i][j]    (i, j)       ：1         ；0        。   
   press[i][j]            ，       (i, j)    ：1      ；
0       。    0  、  0     7            ，    ，   
             、       。   30               
   。     press    2
30
   。                     ，
      、   。        ，              。     
      press，          。
      ，     press       ，     press            
    ，          ：
        (1, j)       ，      (2, j)   ，  press[2][j]    1；
        (1, j)       ，      (2, j)   ，  press[2][j]    0。
     press    、          ，             。    
   、 、               ，            。    ，     press   、 、    。
  ，      press        ，             ，      
      。press        2 6
   ，          press   ，    
          。     2 6
           ：          press
            ，            ，      。

コード実装:

#include
#include
#include
#include
using namespace std;
int press[6][8];
int puzzle[6][8];
bool guess()
{
	int i,j;
	for(i=2;i<=5;i++)
	{
		for(j=1;j<=6;j++)
		{
		//       ，           
			press[i][j]=(press[i-1][j]+puzzle[i-1][j]+press[i-1][j-1]+press[i-2][j]+press[i-1][j+1])%2;
		}
	}
	for(j=1;j<=6;j++)
	{
	//            
		if(press[5][j]!=(puzzle[5][j]+press[5][j-1]+press[5][j+1]+press[4][j])%2)
			return false;
	}
	return true;
}
void process()
{
	int c;
	for(c=1;c<=6;c++)press[1][c]=0;
	while(!guess())
	{
		press[1][1]++;
		c=1;
		while(press[1][c]>1)
		{
			press[1][c]=0;
			c++;
			press[1][c]++;
		}
	}
}
int main()
{
	int i,n,j;
	for(i=0;i<8;i++)
		press[0][i]=puzzle[0][i]=0;
	for(i=1;i<6;i++)
		press[i][0]=puzzle[i][0]=press[i][7]=puzzle[i][7]=0;
	for(i=1;i<=5;i++)
		for(j=1;j<=6;j++)
			scanf("%d",&puzzle[i][j]);
	process();
	for(i=1;i<=5;i++)
	{
		for(j=1;j<=6;j++)printf("%d ",press[i][j]);
		printf("
");
	}
}

元ブロガーが上手だと言わざるを得ません!原帖:http://blog.sina.com.cn/s/blog_7393daaf0100svoo.html