Poj 1753 Flip Game Gauss消元
34226 ワード
タイトル接続:
http://poj.org/problem?id=1753
テーマ:
1つの4*4の格子があって、それぞれの格子は黒あるいは白色で、その中の1つの格子を反転してそれを変色させて、その上下左右の格子を牽引して同時に変色して、最終的に少なくともいくつの格子を反転してやっと4*4の格子を同じ色に変えることができますか?
問題解決の考え方:
実はこのテーマはどのようにしてすべてすることができて、暴捜することができて、位の演算、dfs、最近ガウスの消元を学んで、ガウスで解いて、16個の格子の広がりの行列は16*17で、階段の行列を求めた後に、列挙して不確定な変元を挙げて、不確定な変元と階段の行列によって確定な変元を求めて、それから操作する回数を統計して、最も良いことを選択します.
ついでにもう一つの暴捜コードを貼って、簡単で乱暴で、はっきりしています
http://poj.org/problem?id=1753
テーマ:
1つの4*4の格子があって、それぞれの格子は黒あるいは白色で、その中の1つの格子を反転してそれを変色させて、その上下左右の格子を牽引して同時に変色して、最終的に少なくともいくつの格子を反転してやっと4*4の格子を同じ色に変えることができますか?
問題解決の考え方:
実はこのテーマはどのようにしてすべてすることができて、暴捜することができて、位の演算、dfs、最近ガウスの消元を学んで、ガウスで解いて、16個の格子の広がりの行列は16*17で、階段の行列を求めた後に、列挙して不確定な変元を挙げて、不確定な変元と階段の行列によって確定な変元を求めて、それから操作する回数を統計して、最も良いことを選択します.
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #include <iostream>
6 using namespace std;
7
8 const int maxn = 20;
9 int det[maxn][maxn], equ, var;
10
11 int gauss ()
12 {
13 int max_i, k, col, cou = 0;
14 int free_num[maxn], free_i[maxn], x[maxn];
15
16 memset (free_i, 0, sizeof(free_i));
17 memset (x, 0, sizeof(x));
18
19 for (k=col=0; k<equ&&col<var; k++, col++)
20 {//
21 max_i = k;
22 for (int i=k+1; i<equ; i++)// col k .
23 if (det[max_i][col] < det[i][col])
24 max_i = i;
25 if (det[max_i][col] == 0)
26 {// col k 0 ， .
27 free_i[col] = 1;
28 x[cou++] = col;
29 k --;
30 continue;
31 }
32 if (max_i != k)
33 for (int i=col; i<=var; i++)
34 swap(det[max_i][i], det[k][i]);
35 for (int i=k+1; i<equ; i++)
36 if (det[i][col])// .
37 for (int j=col; j<=var; j++)
38 det[i][j] ^= det[k][j];
39 }
40 for (int i=k; i<equ; i++)
41 if (det[i][var])//
42 return maxn;
43 int res = maxn, num = 1<<cou;
44 for (int i=0; i<num; i++)
45 {
46 int nu = 0, m = i;
47 memset (free_num, 0, sizeof(free_num));
48 for (int j=0; j<cou; j++)
49 {//
50 if (m % 2)
51 {
52 free_num[x[j]] = 1;
53 nu ++;
54 }
55 m /= 2;
56 }
57 for (int j=k-1; j>=0; j--)
58 if (!free_i[j])
59 {// ，
60 int temp = det[j][16];
61 for (int l=j+1; l<var; l++)
62 if (det[j][l])
63 temp ^= free_num[l];
64 free_num[j] = temp;
65 if (temp)
66 nu ++;
67 }
68 res = min (res, nu);
69 }
70 return res;
71 }
72 int main ()
73 {
74 int map[maxn], j = 0;
75 char str[maxn];
76
77 equ = var = 16;
78 for (int i=0; i<4; i++)
79 {
80 scanf ("%s", str);
81 for (int l=0; str[l]; l++)
82 if (str[l] == 'b')
83 map[j++]=1;
84 else
85 map[j++] = 0;
86 }
87
88 memset (det, 0, sizeof(det));
89 for (int i=0; i<16; i++)
90 {//
91 det[i][i] = 1;
92 det[i][16] = map[i];
93 if (i < 12)
94 det[i][i+4] = 1;
95 if (i > 3)
96 det[i][i-4] = 1;
97 if (i % 4 != 0)
98 det[i][i-1] = 1;
99 if (i % 4 != 3)
100 det[i][i+1] = 1;
101 }
102 int res = gauss ();
103 memset (det, 0, sizeof(det));
104 for (int i=0; i<16; i++)
105 {
106 det[i][i] = 1;
107 det[i][16] = 1 - map[i];
108 if (i < 12)
109 det[i][i+4] = 1;
110 if (i > 3)
111 det[i][i-4] = 1;
112 if (i % 4 != 0)
113 det[i][i-1] = 1;
114 if (i % 4 != 3)
115 det[i][i+1] = 1;
116 }
117 res = min (res, gauss());
118 if (res == maxn)
119 printf ("Impossible
");
120 else
121 printf ("%d
", res);
122 return 0;
123 }ついでにもう一つの暴捜コードを貼って、簡単で乱暴で、はっきりしています
1 #include <iostream>
2 #include <algorithm>
3 #include <cstdio>
4 #include <cstring>
5 #include <cstdlib>
6
7 #define N 5
8 #define INF 0x3f3f3f
9 using namespace std;
10
11 char a[N][N], map[N][N];
12 int dir[][2] = {0,0, 1,0, 0,1, -1,0, 0,-1};
13
14 int change(char ch, int num);
15 void turn (int x, int y, char X[][N]);
16 void init ();
17
18 int main ()
19 {
20 int i, j, min, sum, num;
21
22 for (i=0; i<4; i++)
23 {
24 scanf ("%s", a[i]);
25 strcpy (map[i], a[i]);
26 }
27
28 min = INF;
29
30 for (i=0; i<16; i++)
31 {
32 sum = i;
33 num = 0;
34 for (j=0; j<4; j++)
35 {
36 if ( sum % 2 )
37 {
38 turn(0, j, map);
39 num ++;
40 }
41 sum /= 2;
42 }
43
44 init();
45 sum = change ('b', num);
46 if (min > sum)
47 min = sum;
48 init();
49 sum = change ('w', num);
50 if (min > sum)
51 min = sum;
52
53 sum = i;
54 for (j=0; j<4; j++)
55 {
56 if ( sum % 2 )
57 {
58 turn (0, j, map);
59 }
60 sum /= 2;
61 }
62 }
63 if (min == INF)
64 printf ("Impossible
");
65 else
66 printf ("%d
", min);
67 return 0;
68 }
69 int change( char ch, int num)
70 {
71 int i, j;
72
73 for (i=1; i<4; i++)
74 for (j=0; j<4; j++)
75 if (a[i-1][j] != ch)
76 {
77 num ++;
78 turn(i, j, a);
79 }
80 for (i=0; i<4; i++)
81 if (a[3][i] != ch)
82 return INF;
83 return num;
84 }
85
86 void turn (int x, int y, char X[][N])
87 {
88 for (int i=0; i<5; i++)
89 {
90 int A = x + dir[i][0];
91 int B = y + dir[i][1];
92
93 if (A >= 0 && A < 4 && B >= 0 && B < 4)
94 {
95 if (X[A][B] == 'w')
96 X[A][B] = 'b';
97 else
98 X[A][B] = 'w';
99 }
100 }
101 }
102
103 void init ()
104 {
105 int i;
106 for (i=0; i<4; i++)
107 strcpy (a[i], map[i]);
108 }