pku1222 EXTENDED LIGHTS OUT

http://poj.org/problem?id=1222
搜索，关灯游戏，可以用高斯消元做
搜索代码：
  1 #include <stdio.h>
  2 #include <string.h>
  3 
  4 int map[8][8], map1[8][8], stack[8][8];
  5 
  6 void change(int i, int j)
  7 {
  8     map1[i][j] ^= 1;
  9     map1[i][j-1] ^= 1;
 10     map1[i][j+1] ^= 1;
 11     map1[i-1][j] ^= 1;
 12     map1[i+1][j] ^= 1;
 13 }
 14 
 15 int check()
 16 {
 17     int i, j;
 18     for(i=1; i<=5; i++)
 19     {
 20         for(j=1; j<=6; j++)
 21         {
 22             map1[i][j] = map[i][j];
 23         }
 24     }
 25     for(j=1; j<=6; j++)
 26     {
 27         if(stack[1][j])
 28         {
 29             change(1, j);
 30         }
 31     }
 32     for(i=2; i<=5; i++)
 33     {
 34         for(j=1; j<=6; j++)
 35         {
 36             stack[i][j] = map1[i-1][j];
 37             if(stack[i][j])
 38             {
 39                 change(i, j);
 40             }
 41         }
 42     }
 43     for(i=1; i<=6; i++)
 44     {
 45         if(map1[5][i])
 46         {
 47             return 0;
 48         }
 49     }
 50     return 1;
 51 }
 52 
 53 int dfs(int i)
 54 {
 55     if(i==7)
 56     {
 57         if(check())
 58         {
 59             return 1;
 60         }
 61         return 0;
 62     }
 63     stack[1][i] = 0;
 64     if(dfs(i+1))
 65     {
 66         return 1;
 67     }
 68     stack[1][i] = 1;
 69     if(dfs(i+1))
 70     {
 71         return 1;
 72     }
 73     return 0;
 74 }
 75 
 76 int main()
 77 {
 78     int t, cases, i, j;
 79     scanf("%d", &t);
 80     for(cases=1; cases<=t; cases++)
 81     {
 82         for(i=1; i<=5; i++)
 83         {
 84             for(j=1; j<=6; j++)
 85             {
 86                 scanf("%d", &map[i][j]);
 87             }
 88         }
 89         dfs(1);
 90         printf("PUZZLE #%d\n", cases);
 91         for(i=1; i<=5; i++)
 92         {
 93             for(j=1; j<=6; j++)
 94             {
 95                 printf(j-6? "%d ": "%d\n", stack[i][j]);
 96             }
 97         }
 98     }
 99     return 0;
100 }