DIV2 1000pt

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

 For i =  to H-:
For j = to W-:
//Get the current colors of cells (i,j) and (i,j+1)
A = Color(i,j) , B = Color(i,j+) If (A,B) == (White, White) Then:
Do nothing.
EndIf
If (A,B) == (Black, White) Then:
Repaint cells (i+,j) and (i+,j+) Black.
EndIf
If (A,B) == (White, Black) Then:
Repaint cells (i+,j) and (i+,j+) White.
EndIf
if (A,B) == (Black, Black) Then:
Swap the colors in cells (i+,j) and (i+,j+).
EndIf
EndFor
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

法一:

 // BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "Algrid.cpp"
#include <sstream>
#include <stdexcept>
#include <functional>
#include <iomanip>
#include <numeric>
#include <fstream>
#include <cctype>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <set>
#include <queue>
#include <bitset>
#include <list>
#include <string>
#include <utility>
#include <map>
#include <ctime>
#include <stack> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define CLR1(x) memset(x, -1, sizeof(x))
#define PB push_back
#define SZ(v) ((int)(v).size())
#define zero(x) (((x)>0?(x):-(x))<eps)
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl
#define CINBEQUICKER std::ios::sync_with_stdio(false) typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long int64; const double eps = 1e-;
const double PI = atan(1.0)*;
const int maxint = ; int n, all, len;
bool flag;
int a[], ans[]; int change(int x, int y)
{
if (x == -) return -; int ta[], tb[];
int idxa = , idxb = ;
for (int i = ; i < len; ++ i){
ta[idxa++] = x & ;
x >>= ;
tb[idxb++] = y & ;
y >>= ;
}
for (int i = len-; i; -- i){
if (!ta[i] && ta[i-]) tb[i] = tb[i-] = ;
if (ta[i] && !ta[i-]) tb[i] = tb[i-] = ;
if (!ta[i] && !ta[i-]) swap(tb[i], tb[i-]);
}
int ret = ;
for (int i = len-; i >= ; -- i)
ret += (tb[i] << i);
return ret;
} void DFS (int x)
{
if (x == n){
flag = ;
return;
} for (int i = ; i < all; ++ i)
if (!flag && change(a[x-], i) == a[x]){
ans[x] = i;
DFS (x+);
if (!flag) ans[x] = -;
}
} class Algrid
{
public:
vector <string> makeProgram(vector <string> A){
len = A[].size();
n = A.size(); all = << len;
for (int i = ; i < n; ++ i){
int tmp = ;
for (int j = len-, k = ; j >= ; -- j, ++ k)
if (A[i][j] == 'W'){
tmp += ( << k);
}
a[i] = tmp;
} CLR1 (ans);
ans[] = a[]; flag = ;
DFS (); vector<string> ret; ret.clear();
string tmp;
for (int i = ; i < n; ++ i){
if (ans[i] == -){
ret.clear(); return ret;
} tmp.clear();
for (int j = len-; j >= ; -- j){
if (ans[i] & (<<j)) tmp.PB ('W');
else tmp.PB('B');
}
ret.PB (tmp);
}
return ret;
} // BEGIN CUT HERE
public:
void run_test(int Case) { if ((Case == -) || (Case == )) test_case_0(); if ((Case == -) || (Case == )) test_case_1(); if ((Case == -) || (Case == )) test_case_2(); if ((Case == -) || (Case == )) test_case_3(); }
//void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0();}
private:
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
void verify_case(int Case, const vector <string> &Expected, const vector <string> &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; } }
void test_case_0() { string Arr0[] = {"WWBBB", "WBBBW"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); string Arr1[] = {"WWWWWWW", "WWWWWWB", "BBBBBBB" }; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, makeProgram(Arg0)); }
void test_case_1() { string Arr0[] = {"BBBBB",
"WBWBW"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); string Arr1[] = {"BBBBB", "WWBWB" }; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, makeProgram(Arg0)); }
void test_case_2() { string Arr0[] = {"BBBB",
"BBBB",
"BBWB",
"WWBB",
"BWBB"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); string Arr1[] = { }; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, makeProgram(Arg0)); }
void test_case_3() { string Arr0[] = {"WWBBBBW",
"BWBBWBB",
"BWBBWBW",
"BWWBWBB"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); string Arr1[] = {"WWBBBBW", "BBBBBWB", "BBBBBBB", "BBBWBBB" }; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, makeProgram(Arg0)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
// freopen( "a.out" , "w" , stdout );
Algrid ___test;
___test.run_test(-);
return ;
}
// END CUT HERE

法二:

 // BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "Algrid.cpp"
#include <sstream>
#include <stdexcept>
#include <functional>
#include <iomanip>
#include <numeric>
#include <fstream>
#include <cctype>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <set>
#include <queue>
#include <bitset>
#include <list>
#include <string>
#include <utility>
#include <map>
#include <ctime>
#include <stack> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define CLR1(x) memset(x, -1, sizeof(x))
#define PB push_back
#define SZ(v) ((int)(v).size())
#define zero(x) (((x)>0?(x):-(x))<eps)
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl
#define CINBEQUICKER std::ios::sync_with_stdio(false) typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long int64; const double eps = 1e-;
const double PI = atan(1.0)*;
const int maxint = ; class Algrid
{
public:
vector <string> makeProgram(vector <string> opt){
vector<string> tmp; tmp.clear();
int n = opt.size(), m = opt[].size();
for (int i = n-; i >= ; -- i){
for (int j = m-; j >= ; -- j){
char a = opt[i][j], b = opt[i][j+];
char &c = opt[i+][j], &d = opt[i+][j+]; if (a == 'B' && b == 'B')
swap (c, d);
if (a == 'B' && b == 'W'){
if (c == 'W' || d == 'W') return tmp;
else d = c = '?';
}
if (a == 'W' && b == 'B'){
if (c == 'B' || d == 'B') return tmp;
else c = d = '?';
}
}
replace (opt[i+].begin(), opt[i+].end(), '?', 'B');
}
return opt;
} // BEGIN CUT HERE
public:
void run_test(int Case) { if ((Case == -) || (Case == )) test_case_0(); if ((Case == -) || (Case == )) test_case_1(); if ((Case == -) || (Case == )) test_case_2(); if ((Case == -) || (Case == )) test_case_3(); }
private:
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
void verify_case(int Case, const vector <string> &Expected, const vector <string> &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; } }
void test_case_0() { string Arr0[] = {"WWWWWWW",
"WWWWWWB",
"BBBBBWW"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); string Arr1[] = {"WWWWWWW", "WWWWWWB", "BBBBBBB" }; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, makeProgram(Arg0)); }
void test_case_1() { string Arr0[] = {"BBBBB",
"WBWBW"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); string Arr1[] = {"BBBBB", "WWBWB" }; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, makeProgram(Arg0)); }
void test_case_2() { string Arr0[] = {"BBBB",
"BBBB",
"BBWB",
"WWBB",
"BWBB"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); string Arr1[] = { }; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, makeProgram(Arg0)); }
void test_case_3() { string Arr0[] = {"WWBBBBW",
"BWBBWBB",
"BWBBWBW",
"BWWBWBB"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); string Arr1[] = {"WWBBBBW", "BBBBBWB", "BBBBBBB", "BBBWBBB" }; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[]))); verify_case(, Arg1, makeProgram(Arg0)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
// freopen( "a.out" , "w" , stdout );
Algrid ___test;
___test.run_test(-);
return ;
}
// END CUT HERE

最新文章

  1. hover 变内容
  2. 【leetcode】Anagrams
  3. Linux大神必备-文本编辑器
  4. JavaScript 编写多线程代码引用Concurrent.Thread.js(转)
  5. Tesseract训练笔记
  6. 使用MongoDB的开源项目
  7. 17.1.2.1 Advantages and Disadvantages of Statement-Based and Row-Based Replication 基于语句和行的复制的优势和劣势
  8. ASP.NET之JSONHelper操作
  9. C# 将窗口移动到指定位置
  10. 5.非关系数据库(Nosql)它mongodb:创建一个集合,导出和导入备份, 数据恢复,进出口
  11. 带您了解mysql CONCAT()函数
  12. oracle导入dmp文件的2种方法
  13. SecureCRT连接虚拟机失败及虚拟机ping不通外网
  14. python-MongoDB 非关系型数据库
  15. Codeforces 946D - Timetable (预处理+分组背包)
  16. Rxjs 修改Observable 里的值
  17. 程序猿CET4和CET6考试攻略
  18. UNIX高级环境编程(7)标准IO函数库 - 二进制文件IO,流定位,创建临时文件和内存流
  19. Twitter.com在用哪些Javascript框架?
  20. 关于vs2015无法启动iis服务

热门文章

  1. 知方可补不足~SQL中的count命令的一些优化措施(百万以上数据明显)
  2. Android ViewPager初探:让页面滑动起来
  3. 【转】配置 VS 2015 开发跨平台手机应用
  4. win7里开始菜单属性里的隐私项无法选择解决方法
  5. 十三、Android学习笔记_Andorid控件样式汇总
  6. private继承
  7. 最清晰的ios消息推送机制教程
  8. PHP漏洞全解(六)-跨网站请求伪造
  9. 筛1-n中每个数的因子(nlogn)
  10. opencv之图像腐蚀
  11. Hibernate + Spring (quartz) 整合懒(延迟)加载问题
  12. jQuery 数据滚动(上下)
  13. Android 初了解
  14. C语言复习0_准备工作
  15. django----Form提交按钮
  16. 搭建自己的docker仓库
  17. C++ map&lt;key , value&gt; key值为指针
  18. Context namespace element &#39;annotation-config&#39; and its parser class [org.springframework.context.annotation.AnnotationConfigBeanDefinitionParser] are only available on JDK 1.5 and higher
  19. JS实现文本框和文本域获取焦点focus()时,光标在本文的末尾
  20. c++版 nms