计算 5*n 板的正确配置（动态编程，C++）
Counting Correct Configurations of a 5*n board (Dynamic Programming, C++)
问题如下：
编写一个程序来确定 5*n 方形网格上 white/black 模式的数量（模数 m），其中不包含任何 p 禁止模式。
输入数据具有以下格式：第一行包含 3 个逗号分隔的整数：
n - 列数，p - 禁止模式数，m - 模数。以下 3*p 行包含 3 个字符长的字符串，由 . 或 x 组成，其中 . 表示白色区域，x 表示黑色区域。这些是禁止的模式，例如：
x..
..x
.xx
这是我解决这个问题的动态算法：
让 3 列 "block" 由 15 位长的位集表示，位映射到列如下（1 == 黑色，0 == 白色）：
0 5 10
1 6 11
2 7 12
3 8 13
4 9 14
读取输入数据并构造所有表示禁止模式的位集（未使用的字段设置为 0）。创建一个布尔值向量，并在每个索引下使用等于禁止模式的二进制表示将值设置为 true。对表示向左移动 1 和 2 的禁止模式的索引执行相同操作（因为禁止模式可能从列的第一行、第二行或第三行开始）。
现在，创建 2 个整数向量，left 和 right，每个向量的大小为 1024 (2^10)。这些向量中的索引表示 2 列的配置 "blocks"。在第 i 次迭代中，left 向量中的值表示有多少不同的正确配置以第 (i-1) 列中该向量的索引表示的 2 列模式结束。现在遍历第 3 列的所有 32 种可能性，并将该列添加到 2 列模式，每次检查这样的 3 列模式是否不包含禁止模式。如果是，则跳到第 3 列的下一个可能性，如果不是，则从表示 3 列模式的前 2 列的 left 向量中获取值并将其添加到 right 表示由第 2 列和第 3 列组成的 2 列模式的向量。在考虑了所有可能的 2 列之后，交换向量，用 0 初始化 right 向量并重复该过程，直到我们到达 n-th 列。
答案是左侧向量中所有字段的总和（因为最后一次操作交换了向量）。
我希望这是清楚的，如果有任何需要澄清的地方，请发表评论。
我的实施 returns 仅当禁用模式在顶行和底行中至少有 1 个 x 时才能得到正确的结果，即：
x..
...
..x
我只是想不通问题出在哪里。如果代码中有任何不清楚的地方，请告诉我，我将编辑此 post 以澄清这一点。
这是我的实现：
http://pastebin.com/2ZPjiyuj
#include <iostream>
#include <vector>
#include <bitset>
#include <stdio.h>
using namespace std;
ostream& operator<< ( ostream& os, const vector<uint32_t>& v )
{
for( auto it = v.begin(); it != v.end(); it++ )
{
os << *it << "\n";
}
return os;
}
inline bitset<15> make_pattern()
{
char field;
bitset<15> pattern;
for( uint32_t offset = 0; offset < 3; offset++ )
{
cin >> field;
if( field == 'x' ) pattern.set(offset);
cin >> field;
if( field == 'x' ) pattern.set(offset + 5);
cin >> field;
if( field == 'x' ) pattern.set(offset + 10);
}
return pattern;
}
int main()
{
uint32_t n, m, p;
cin >> n;
cin >> p;
cin >> m;
vector<bool> forbidden_patterns( 33000 );
for( uint32_t i = 0; i < p; i++ )
{
auto pattern = make_pattern();
forbidden_patterns[pattern.to_ulong()] = true; // true := forbidden; false := allowed.
forbidden_patterns[(pattern << 1).to_ulong()] = true;
forbidden_patterns[(pattern << 2).to_ulong()] = true;
//cout << forbidden_patterns[(pattern<<3).to_ulong()];
//cout << pattern.to_ulong();
}
for( uint32_t i = 0; i< 33000; i++ ) //checking the contents of the forbidden_patterns vector
{
bitset<15> bs = i;
if(forbidden_patterns[i] == true)
cout << bs << "\n";
}
cout << "\n\n";
//bitmasks for setting 2 rows of a 3 column pattern to 0;
bitset<15> bottom_rows_reset_mask;
bottom_rows_reset_mask.set(3); bottom_rows_reset_mask.set(8); bottom_rows_reset_mask.set(13);
bottom_rows_reset_mask.set(4); bottom_rows_reset_mask.set(9); bottom_rows_reset_mask.set(14);
bottom_rows_reset_mask = ~bottom_rows_reset_mask;
bitset<15> top_rows_reset_mask;
top_rows_reset_mask.set(0); top_rows_reset_mask.set(5); top_rows_reset_mask.set(10);
top_rows_reset_mask.set(1); top_rows_reset_mask.set(6); top_rows_reset_mask.set(11);
top_rows_reset_mask = ~top_rows_reset_mask;
bitset<15> top_and_bottom_reset_mask;
top_and_bottom_reset_mask.set(0); top_and_bottom_reset_mask.set(5); top_and_bottom_reset_mask.set(10);
top_and_bottom_reset_mask.set(4); top_and_bottom_reset_mask.set(9); top_and_bottom_reset_mask.set(14);
top_and_bottom_reset_mask = ~top_and_bottom_reset_mask;
vector<uint32_t> left( 1024, 1 );
vector<uint32_t> right( 1024, 0 );
for( uint32_t column = 3; column <= n; column++ )
{
for( uint32_t first_2_columns = 0; first_2_columns < 1024; first_2_columns++ )
{
if( left[first_2_columns] == 0 ) continue;
for( uint32_t third_column = 0; third_column < 32; third_column++ )
{
bitset<15> t_patt = (first_2_columns | third_column << 10) & top_and_bottom_reset_mask.to_ulong();
//cout << t_patt << "\n"; //getchar();
if( forbidden_patterns[t_patt.to_ulong()] == true )
{
//cout << t_patt << "\n"; getchar();
continue;
}
t_patt = (first_2_columns | third_column << 10) & bottom_rows_reset_mask.to_ulong();
//cout << t_patt << "\n"; //getchar();
if( forbidden_patterns[t_patt.to_ulong()] == true )
{
//cout << t_patt << "\n"; getchar();
continue;
}
t_patt = (first_2_columns | third_column << 10) & top_rows_reset_mask.to_ulong();
//cout << t_patt << "\n"; //getchar();
if( forbidden_patterns[t_patt.to_ulong()] == true )
{
//cout << t_patt << "\n"; getchar();
continue;
}
t_patt = first_2_columns | third_column << 10;
//cout << t_patt << "\n";
auto next_2_column_pattern = (t_patt >> 5).to_ulong();
//t_patt = next_2_column_pattern; cout << t_patt << "\n"; getchar();
right[next_2_column_pattern] = (right[next_2_column_pattern] + left[first_2_columns]) % m;
}
}
left.swap(right);
right.assign(1024, 0u);
}
uint32_t sum = 0;
for( int i = 0; i < 1024; i++ )
sum = (sum + left[i]) % m;
cout << sum;
}
我已经设法自己解决了这个问题（尽管 PaulMcKenzie 非常感谢你为我指明了正确的方向）。
问题是我的算法没有区分向左移动 0、1 或 2 位的禁止模式。当输入数据的模式在底部和顶部的行中仅包含至少 1 个 x 时，一切都很好，但是一旦在顶部或底部的行中给出了仅包含 .'s 的模式，程序就会开始出现异常。
考虑一个顶行没有任何 x 的禁止模式 - 将其向左移动 1 位后，该模式的前两行变为零。我程序中最内层循环的一个 ifs 将被测试模式的前 2 行设置为零，并将剩余的内容与 forbidden_patterns 向量进行比较，其中它可能与其中一个模式匹配，而没有任何 x's顶行向左移动 1 位！这在逻辑上是错误的，因为已向左移动 1 位的禁止模式从第 2 行开始，而前两行为零的模式只能包含从第 3 行开始的禁止模式。这导致我的程序更频繁地进入最内层循环的 ifs，因此 "under-counting" 正确的配置。
这个问题的解决方案非常简单 - 将 forbidden_patterns 向量分成 3 个向量 - 1 个包含没有任何移位的模式，1 个包含向左移位 1 的模式，第 3 个包含向左移位 2 的模式左边。然后将在最内层循环的 ifs 中使用适当的向量。
固定代码：
http://pastebin.com/WCb8eB9F
#include <iostream>
#include <vector>
#include <bitset>
#include <stdio.h>
using namespace std;
inline bitset<15> make_pattern()
{
char field;
bitset<15> pattern;
for( uint32_t offset = 0; offset < 3; offset++ )
{
cin >> field;
if( field == 'x' ) pattern.set(offset);
cin >> field;
if( field == 'x' ) pattern.set(offset + 5);
cin >> field;
if( field == 'x' ) pattern.set(offset + 10);
}
return pattern;
}
int main()
{
uint32_t n, m, p;
cin >> n;
cin >> p;
cin >> m;
vector<bool> top_forbidden_patterns( 32768 ); // top_forbidden patterns can only be compared to 3 column patterns that have the top 2 rows zeroed.
vector<bool> mid_forbidden_patterns( 32768 ); // mid_forbidden patterns can only be compared to 3 column patterns that have the top and bottom row zeroed.
vector<bool> bottom_forbidden_patterns( 32768 ); // bottom_forbidden patterns can only be compared to 3 column patterns that have the bottom 2 rows zeroed.
for( uint32_t i = 0; i < p; i++ )
{
auto pattern = make_pattern();
bottom_forbidden_patterns[pattern.to_ulong()] = true; // true := forbidden; false := allowed.
mid_forbidden_patterns[(pattern << 1).to_ulong()] = true;
top_forbidden_patterns[(pattern << 2).to_ulong()] = true;
}
//bitmasks for setting 2 rows of a 3 column pattern to 0;
bitset<15> bottom_rows_reset_mask;
bottom_rows_reset_mask.set(3); bottom_rows_reset_mask.set(8); bottom_rows_reset_mask.set(13);
bottom_rows_reset_mask.set(4); bottom_rows_reset_mask.set(9); bottom_rows_reset_mask.set(14);
bottom_rows_reset_mask = ~bottom_rows_reset_mask;
bitset<15> top_rows_reset_mask;
top_rows_reset_mask.set(0); top_rows_reset_mask.set(5); top_rows_reset_mask.set(10);
top_rows_reset_mask.set(1); top_rows_reset_mask.set(6); top_rows_reset_mask.set(11);
top_rows_reset_mask = ~top_rows_reset_mask;
bitset<15> top_and_bottom_reset_mask;
top_and_bottom_reset_mask.set(0); top_and_bottom_reset_mask.set(5); top_and_bottom_reset_mask.set(10);
top_and_bottom_reset_mask.set(4); top_and_bottom_reset_mask.set(9); top_and_bottom_reset_mask.set(14);
top_and_bottom_reset_mask = ~top_and_bottom_reset_mask;
vector<uint32_t> left( 1024, 1 );
vector<uint32_t> right( 1024, 0 );
for( uint32_t column = 3; column <= n; column++ )
{
for( uint32_t first_2_columns = 0; first_2_columns < 1024; first_2_columns++ )
{
if( left[first_2_columns] == 0 ) continue;
for( uint32_t third_column = 0; third_column < 32; third_column++ )
{
bitset<15> t_patt = (first_2_columns | third_column << 10) & top_and_bottom_reset_mask.to_ulong();
if( mid_forbidden_patterns[t_patt.to_ulong()] == true )
continue;
t_patt = (first_2_columns | third_column << 10) & bottom_rows_reset_mask.to_ulong();
if( bottom_forbidden_patterns[t_patt.to_ulong()] == true )
continue;
t_patt = (first_2_columns | third_column << 10) & top_rows_reset_mask.to_ulong();
if( top_forbidden_patterns[t_patt.to_ulong()] == true )
continue;
t_patt = first_2_columns | third_column << 10;
auto next_2_column_pattern = (t_patt >> 5).to_ulong();
right[next_2_column_pattern] = (right[next_2_column_pattern] + left[first_2_columns]) % m;
}
}
left.swap(right);
right.assign(1024, 0u);
}
uint32_t sum = 0;
for( auto el : left )
sum = (sum + el) % m;
cout << sum;
return 0;
}
问题如下：
编写一个程序来确定 5*n 方形网格上 white/black 模式的数量（模数 m），其中不包含任何 p 禁止模式。
输入数据具有以下格式：第一行包含 3 个逗号分隔的整数：
n - 列数，p - 禁止模式数，m - 模数。以下 3*p 行包含 3 个字符长的字符串，由 . 或 x 组成，其中 . 表示白色区域，x 表示黑色区域。这些是禁止的模式，例如：
x..
..x
.xx
这是我解决这个问题的动态算法：
让 3 列 "block" 由 15 位长的位集表示，位映射到列如下（1 == 黑色，0 == 白色）：
0 5 10
1 6 11
2 7 12
3 8 13
4 9 14
读取输入数据并构造所有表示禁止模式的位集（未使用的字段设置为 0）。创建一个布尔值向量，并在每个索引下使用等于禁止模式的二进制表示将值设置为 true。对表示向左移动 1 和 2 的禁止模式的索引执行相同操作（因为禁止模式可能从列的第一行、第二行或第三行开始）。
现在，创建 2 个整数向量，left 和 right，每个向量的大小为 1024 (2^10)。这些向量中的索引表示 2 列的配置 "blocks"。在第 i 次迭代中，left 向量中的值表示有多少不同的正确配置以第 (i-1) 列中该向量的索引表示的 2 列模式结束。现在遍历第 3 列的所有 32 种可能性，并将该列添加到 2 列模式，每次检查这样的 3 列模式是否不包含禁止模式。如果是，则跳到第 3 列的下一个可能性，如果不是，则从表示 3 列模式的前 2 列的 left 向量中获取值并将其添加到 right 表示由第 2 列和第 3 列组成的 2 列模式的向量。在考虑了所有可能的 2 列之后，交换向量，用 0 初始化 right 向量并重复该过程，直到我们到达 n-th 列。
答案是左侧向量中所有字段的总和（因为最后一次操作交换了向量）。
我希望这是清楚的，如果有任何需要澄清的地方，请发表评论。
我的实施 returns 仅当禁用模式在顶行和底行中至少有 1 个 x 时才能得到正确的结果，即：
x..
...
..x
我只是想不通问题出在哪里。如果代码中有任何不清楚的地方，请告诉我，我将编辑此 post 以澄清这一点。
这是我的实现： http://pastebin.com/2ZPjiyuj
#include <iostream>
#include <vector>
#include <bitset>
#include <stdio.h>
using namespace std;
ostream& operator<< ( ostream& os, const vector<uint32_t>& v )
{
for( auto it = v.begin(); it != v.end(); it++ )
{
os << *it << "\n";
}
return os;
}
inline bitset<15> make_pattern()
{
char field;
bitset<15> pattern;
for( uint32_t offset = 0; offset < 3; offset++ )
{
cin >> field;
if( field == 'x' ) pattern.set(offset);
cin >> field;
if( field == 'x' ) pattern.set(offset + 5);
cin >> field;
if( field == 'x' ) pattern.set(offset + 10);
}
return pattern;
}
int main()
{
uint32_t n, m, p;
cin >> n;
cin >> p;
cin >> m;
vector<bool> forbidden_patterns( 33000 );
for( uint32_t i = 0; i < p; i++ )
{
auto pattern = make_pattern();
forbidden_patterns[pattern.to_ulong()] = true; // true := forbidden; false := allowed.
forbidden_patterns[(pattern << 1).to_ulong()] = true;
forbidden_patterns[(pattern << 2).to_ulong()] = true;
//cout << forbidden_patterns[(pattern<<3).to_ulong()];
//cout << pattern.to_ulong();
}
for( uint32_t i = 0; i< 33000; i++ ) //checking the contents of the forbidden_patterns vector
{
bitset<15> bs = i;
if(forbidden_patterns[i] == true)
cout << bs << "\n";
}
cout << "\n\n";
//bitmasks for setting 2 rows of a 3 column pattern to 0;
bitset<15> bottom_rows_reset_mask;
bottom_rows_reset_mask.set(3); bottom_rows_reset_mask.set(8); bottom_rows_reset_mask.set(13);
bottom_rows_reset_mask.set(4); bottom_rows_reset_mask.set(9); bottom_rows_reset_mask.set(14);
bottom_rows_reset_mask = ~bottom_rows_reset_mask;
bitset<15> top_rows_reset_mask;
top_rows_reset_mask.set(0); top_rows_reset_mask.set(5); top_rows_reset_mask.set(10);
top_rows_reset_mask.set(1); top_rows_reset_mask.set(6); top_rows_reset_mask.set(11);
top_rows_reset_mask = ~top_rows_reset_mask;
bitset<15> top_and_bottom_reset_mask;
top_and_bottom_reset_mask.set(0); top_and_bottom_reset_mask.set(5); top_and_bottom_reset_mask.set(10);
top_and_bottom_reset_mask.set(4); top_and_bottom_reset_mask.set(9); top_and_bottom_reset_mask.set(14);
top_and_bottom_reset_mask = ~top_and_bottom_reset_mask;
vector<uint32_t> left( 1024, 1 );
vector<uint32_t> right( 1024, 0 );
for( uint32_t column = 3; column <= n; column++ )
{
for( uint32_t first_2_columns = 0; first_2_columns < 1024; first_2_columns++ )
{
if( left[first_2_columns] == 0 ) continue;
for( uint32_t third_column = 0; third_column < 32; third_column++ )
{
bitset<15> t_patt = (first_2_columns | third_column << 10) & top_and_bottom_reset_mask.to_ulong();
//cout << t_patt << "\n"; //getchar();
if( forbidden_patterns[t_patt.to_ulong()] == true )
{
//cout << t_patt << "\n"; getchar();
continue;
}
t_patt = (first_2_columns | third_column << 10) & bottom_rows_reset_mask.to_ulong();
//cout << t_patt << "\n"; //getchar();
if( forbidden_patterns[t_patt.to_ulong()] == true )
{
//cout << t_patt << "\n"; getchar();
continue;
}
t_patt = (first_2_columns | third_column << 10) & top_rows_reset_mask.to_ulong();
//cout << t_patt << "\n"; //getchar();
if( forbidden_patterns[t_patt.to_ulong()] == true )
{
//cout << t_patt << "\n"; getchar();
continue;
}
t_patt = first_2_columns | third_column << 10;
//cout << t_patt << "\n";
auto next_2_column_pattern = (t_patt >> 5).to_ulong();
//t_patt = next_2_column_pattern; cout << t_patt << "\n"; getchar();
right[next_2_column_pattern] = (right[next_2_column_pattern] + left[first_2_columns]) % m;
}
}
left.swap(right);
right.assign(1024, 0u);
}
uint32_t sum = 0;
for( int i = 0; i < 1024; i++ )
sum = (sum + left[i]) % m;
cout << sum;
}
我已经设法自己解决了这个问题（尽管 PaulMcKenzie 非常感谢你为我指明了正确的方向）。
问题是我的算法没有区分向左移动 0、1 或 2 位的禁止模式。当输入数据的模式在底部和顶部的行中仅包含至少 1 个 x 时，一切都很好，但是一旦在顶部或底部的行中给出了仅包含 .'s 的模式，程序就会开始出现异常。
考虑一个顶行没有任何 x 的禁止模式 - 将其向左移动 1 位后，该模式的前两行变为零。我程序中最内层循环的一个 ifs 将被测试模式的前 2 行设置为零，并将剩余的内容与 forbidden_patterns 向量进行比较，其中它可能与其中一个模式匹配，而没有任何 x's顶行向左移动 1 位！这在逻辑上是错误的，因为已向左移动 1 位的禁止模式从第 2 行开始，而前两行为零的模式只能包含从第 3 行开始的禁止模式。这导致我的程序更频繁地进入最内层循环的 ifs，因此 "under-counting" 正确的配置。
这个问题的解决方案非常简单 - 将 forbidden_patterns 向量分成 3 个向量 - 1 个包含没有任何移位的模式，1 个包含向左移位 1 的模式，第 3 个包含向左移位 2 的模式左边。然后将在最内层循环的 ifs 中使用适当的向量。
固定代码： http://pastebin.com/WCb8eB9F
#include <iostream>
#include <vector>
#include <bitset>
#include <stdio.h>
using namespace std;
inline bitset<15> make_pattern()
{
char field;
bitset<15> pattern;
for( uint32_t offset = 0; offset < 3; offset++ )
{
cin >> field;
if( field == 'x' ) pattern.set(offset);
cin >> field;
if( field == 'x' ) pattern.set(offset + 5);
cin >> field;
if( field == 'x' ) pattern.set(offset + 10);
}
return pattern;
}
int main()
{
uint32_t n, m, p;
cin >> n;
cin >> p;
cin >> m;
vector<bool> top_forbidden_patterns( 32768 ); // top_forbidden patterns can only be compared to 3 column patterns that have the top 2 rows zeroed.
vector<bool> mid_forbidden_patterns( 32768 ); // mid_forbidden patterns can only be compared to 3 column patterns that have the top and bottom row zeroed.
vector<bool> bottom_forbidden_patterns( 32768 ); // bottom_forbidden patterns can only be compared to 3 column patterns that have the bottom 2 rows zeroed.
for( uint32_t i = 0; i < p; i++ )
{
auto pattern = make_pattern();
bottom_forbidden_patterns[pattern.to_ulong()] = true; // true := forbidden; false := allowed.
mid_forbidden_patterns[(pattern << 1).to_ulong()] = true;
top_forbidden_patterns[(pattern << 2).to_ulong()] = true;
}
//bitmasks for setting 2 rows of a 3 column pattern to 0;
bitset<15> bottom_rows_reset_mask;
bottom_rows_reset_mask.set(3); bottom_rows_reset_mask.set(8); bottom_rows_reset_mask.set(13);
bottom_rows_reset_mask.set(4); bottom_rows_reset_mask.set(9); bottom_rows_reset_mask.set(14);
bottom_rows_reset_mask = ~bottom_rows_reset_mask;
bitset<15> top_rows_reset_mask;
top_rows_reset_mask.set(0); top_rows_reset_mask.set(5); top_rows_reset_mask.set(10);
top_rows_reset_mask.set(1); top_rows_reset_mask.set(6); top_rows_reset_mask.set(11);
top_rows_reset_mask = ~top_rows_reset_mask;
bitset<15> top_and_bottom_reset_mask;
top_and_bottom_reset_mask.set(0); top_and_bottom_reset_mask.set(5); top_and_bottom_reset_mask.set(10);
top_and_bottom_reset_mask.set(4); top_and_bottom_reset_mask.set(9); top_and_bottom_reset_mask.set(14);
top_and_bottom_reset_mask = ~top_and_bottom_reset_mask;
vector<uint32_t> left( 1024, 1 );
vector<uint32_t> right( 1024, 0 );
for( uint32_t column = 3; column <= n; column++ )
{
for( uint32_t first_2_columns = 0; first_2_columns < 1024; first_2_columns++ )
{
if( left[first_2_columns] == 0 ) continue;
for( uint32_t third_column = 0; third_column < 32; third_column++ )
{
bitset<15> t_patt = (first_2_columns | third_column << 10) & top_and_bottom_reset_mask.to_ulong();
if( mid_forbidden_patterns[t_patt.to_ulong()] == true )
continue;
t_patt = (first_2_columns | third_column << 10) & bottom_rows_reset_mask.to_ulong();
if( bottom_forbidden_patterns[t_patt.to_ulong()] == true )
continue;
t_patt = (first_2_columns | third_column << 10) & top_rows_reset_mask.to_ulong();
if( top_forbidden_patterns[t_patt.to_ulong()] == true )
continue;
t_patt = first_2_columns | third_column << 10;
auto next_2_column_pattern = (t_patt >> 5).to_ulong();
right[next_2_column_pattern] = (right[next_2_column_pattern] + left[first_2_columns]) % m;
}
}
left.swap(right);
right.assign(1024, 0u);
}
uint32_t sum = 0;
for( auto el : left )
sum = (sum + el) % m;
cout << sum;
return 0;
}