DIV2 1000pt

题意：对于一个n*m的矩阵，每个格子都有一个颜色B或者W。对矩阵A执行以下程序后变成矩阵B。给出矩阵B，求A。(若有多种情况，输出字典序最小的)。(n,m <= 16)

1 For i = 0 to H-2: 2     For j = 0 to W-2: 3         //Get the current colors of cells (i,j) and (i,j+1) 4         A = Color(i,j) , B = Color(i,j+1) 5  6         If (A,B) == (White, White) Then: 7              Do nothing. 8         EndIf 9         If (A,B) == (Black, White) Then: 10              Repaint cells (i+1,j) and (i+1,j+1) Black.11         EndIf12         If (A,B) == (White, Black) Then:13              Repaint cells (i+1,j) and (i+1,j+1) White.14         EndIf15         if (A,B) == (Black, Black) Then:16              Swap the colors in cells (i+1,j) and (i+1,j+1).17         EndIf18     EndFor19 EndFor

解法：

　　　法一，水解：首先注意到两点，一是在读取矩阵A的第i行的时候，对其第i+1行进行操作，二是矩阵A和矩阵B的第一行必然相同。

　　　所以，直接暴力DFS即可。由于每行最多只有16个，所以可以压缩状态来做。

　　　法二：比较考查思维的方法。首先仍然要注意到，读第i行时处理第i+1行，所以每行可以单独分析。其次，在读i处理i+1行时，有两种操作，对i+1行的某两个格子染色或者交换他们的颜色。若在读i行时对i+1行的某两个格子染色，则他们之前(在A矩阵中的时候)是什么颜色就不影响了，考虑到要字典序最小，所以应该让他们颜色为'B'。而其他没有被染色的格子，他们需要与变换后的位置的相应元素相同。

　　　这样的方法很巧，而且倒着写比较好写。

tag:think, good

法一：

 

1 // BEGIN CUT HERE  2 /*  3  * Author:  plum rain  4  * score :  5  */  6 /*  7   8  */  9 // END CUT HERE 10 #line 11 "Algrid.cpp" 11 #include 
      
        12 #include 
       
         13 #include 
        
          14 #include 
         
           15 #include 
          
            16 #include 
           
             17 #include 
            
              18 #include 
             
               19 #include 
              
                20 #include 
               
                 21 #include 
                
                  22 #include 
                 
                   23 #include 
                  
                    24 #include 
                   
                     25 #include 
                    
                      26 #include 
                     
                       27 #include 
                      
                        28 #include 
                       
                         29 #include 
                        
                          30 #include 
                         
                           31 #include 
                          

VI; 47 typedef vector

VS; 48 typedef vector

VD; 49 typedef long long int64; 50 51 const double eps = 1e-8; 52 const double PI = atan(1.0)*4; 53 const int maxint = 2139062143; 54 55 int n, all, len; 56 bool flag; 57 int a[100], ans[100]; 58 59 int change(int x, int y) 60 { 61 if (x == -1) return -1; 62 63 int ta[50], tb[50]; 64 int idxa = 0, idxb = 0; 65 for (int i = 0; i < len; ++ i){ 66 ta[idxa++] = x & 1; 67 x >>= 1; 68 tb[idxb++] = y & 1; 69 y >>= 1; 70 } 71 for (int i = len-1; i; -- i){ 72 if (!ta[i] && ta[i-1]) tb[i] = tb[i-1] = 0; 73 if (ta[i] && !ta[i-1]) tb[i] = tb[i-1] = 1; 74 if (!ta[i] && !ta[i-1]) swap(tb[i], tb[i-1]); 75 } 76 int ret = 0; 77 for (int i = len-1; i >= 0; -- i) 78 ret += (tb[i] << i); 79 return ret; 80 } 81 82 void DFS (int x) 83 { 84 if (x == n){ 85 flag = 1; 86 return; 87 } 88 89 for (int i = 0; i < all; ++ i) 90 if (!flag && change(a[x-1], i) == a[x]){ 91 ans[x] = i; 92 DFS (x+1); 93 if (!flag) ans[x] = -1; 94 } 95 } 96 97 class Algrid 98 { 99 public:100 vector

makeProgram(vector

A){101 len = A[0].size();102 n = A.size(); all = 1 << len;103 for (int i = 0; i < n; ++ i){104 int tmp = 0;105 for (int j = len-1, k = 0; j >= 0; -- j, ++ k)106 if (A[i][j] == 'W'){107 tmp += (1 << k);108 }109 a[i] = tmp;110 }111 112 CLR1 (ans);113 ans[0] = a[0];114 115 flag = 0;116 DFS (1);117 118 vector

ret; ret.clear();119 string tmp;120 for (int i = 0; i < n; ++ i){121 if (ans[i] == -1){122 ret.clear(); return ret;123 }124 125 tmp.clear();126 for (int j = len-1; j >= 0; -- j){127 if (ans[i] & (1<

string print_array(const vector

&V) { ostringstream os; os << "{ "; for (typename vector

::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }141 void verify_case(int Case, const vector

&Expected, const vector

&Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: " << print_array(Expected) << endl; cerr << "\tReceived: " << print_array(Received) << endl; } }142 void test_case_0() { string Arr0[] = { "WWBBB", "WBBBW"}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = { "WWWWWWW", "WWWWWWB", "BBBBBBB" }; vector

Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(0, Arg1, makeProgram(Arg0)); }143 void test_case_1() { string Arr0[] = { "BBBBB",144 "WBWBW"}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = { "BBBBB", "WWBWB" }; vector

Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(1, Arg1, makeProgram(Arg0)); }145 void test_case_2() { string Arr0[] = { "BBBB",146 "BBBB",147 "BBWB",148 "WWBB",149 "BWBB"}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = { }; vector

Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(2, Arg1, makeProgram(Arg0)); }150 void test_case_3() { string Arr0[] = { "WWBBBBW",151 "BWBBWBB",152 "BWBBWBW",153 "BWWBWBB"}; vector

Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = { "WWBBBBW", "BBBBBWB", "BBBBBBB", "BBBWBBB" }; vector

Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(3, Arg1, makeProgram(Arg0)); }154 155 // END CUT HERE156 157 };158 159 // BEGIN CUT HERE160 int main()161 {162 // freopen( "a.out" , "w" , stdout ); 163 Algrid ___test;164 ___test.run_test(-1);165 return 0;166 }167 // END CUT HERE