我正在尝试解决算法问题，但我找不到解决方案...
任务是输出达到特定灯具配置所需的最少步数。
有两排灯，N < 10000 列，像这样：
11011
11011
或者
11101101111000101010
01111101100000010100
这些灯可以“开”（1）或“关”（0）。
从全关 (0) 开始，程序必须输出达到所需配置所需的步数。
一个步骤可以是：
我认为算法应该简单地计算完全关闭灯所需的步骤数，这与“正确”顺序相同。另外我的猜测是尝试找到“洞”，即多个具有相同状态的灯的序列，然后切换它们。但它变得复杂，因为有两行......
但是在那之后我完全迷失了，我需要一些帮助......
OP 最近发布了原始问题陈述的链接，结果证明您可以来回切换灯光。我的以下解决方案仅在您仅被允许打开灯时才有效。
让我们定义：
U[i] := i-th light in the upper row.
L[i] := i-th light in the lower row.
A[i][j] := subconfiguration of the input configuration where you have i lamps in the upper row and j lamps in the lower row.
例如，如果开始状态是：
11101101111000101010
01111101100000010100
然后A[5][2]是：
11101
01
其次，让我们定义：
f(i, j) := minimum number of moves to switch all lights off in A[i][j]
你对计算感兴趣f(n, n)
此外，让我们定义：
RU[i] := maximal consecutive run of 1's in the upper row ending in the i-th position.
RL[i] := maximal consecutive run of 1's in the lower row ending in the i-th position.
例如，如果开始状态是：
11101101111000101010
01111101100000010100
那么RU[1] = 1, RU[3] = 3,RU[4] = 0
您可以及时从左到右计算 RU 和 RL O(n)。
首先，观察如果上排末尾A[i][j]有零，下排末尾有零，那么因为最后一个和灯已经关闭。k_1k_2f(i, j) = f(i - k_1, j - k_2)k_1k_2
请注意，如果要计算f(i, j)，则有 3 种情况：
当然，基本情况是f(0, 0)，它需要 0 步。
然后为了计算f(i, j)：
if U[i] is switched off: //skip zeros at the end of the upper row
compute f(i - 1, j)
else if L[j] is switched off: //skip zeros at the end of the lower row
compute f(i, j - 1)
else
if i == j // U[i] and L[j] are switched on because we skipped zeros at the end
f(i, j) = min(f(i - RU[i], j), f(i, j - RL[j]), f(i - 1, j - 1)) + 1
else:
f(i, j) = min(f(i - RU[i], j), f(i, j - RL[j])) + 1
为了避免在递归调用期间f进行相同的i多次j计算，只需将已经计算的结果存储f在哈希表中并将它们返回O(1)而不是再次计算。
简单的上限当然O(n^2)是因为最多有O(n^2)子问题。
这是一个甜蜜的案例std::bitset！
好的，由于我第一次严重误解，我决定做一个简单的启发式。
////////////////////////////////////////////////////
// The solver with a single, simple heuristic:
//
// If there's a hole in a range for row1 where row2 is to have a `1`, we might
// benefit from toggling both rows in advance, because it might result in a
// longer stretch to toggle in the first row
//
// An obvious improvement would to be to try with rows swapped as well.
//
// (As a bonus, all solutions are verified)
int solve(std::ostream& os, bitset row1, bitset row2)
{
auto candidates = row2 & ~row1;
int best_count = row1.size() + 1; // or INT_MAX or similar
bitset best_edits;
for (auto const& edits : combinations(candidates))
{
std::stringstream steps_stream;
int count = emit_steps(steps_stream, row1, row2, edits);
assert(verify(steps_stream, row1, row2, false));
if (count < best_count)
{
best_edits = edits;
best_count = count;
}
}
return emit_steps(os, row1, row2, best_edits);
}
此solve(...)方法现在发出一个步骤脚本，该脚本已使用我原始答案中的解释器（修改版本）进行验证：
// test driver reading the target configuration from stdin
// and displaying the 'best found' solution with intermediate steps
int main()
{
bitset row1, row2;
if (std::cin >> row1 >> row2)
{
std::stringstream steps;
int number = solve(steps, row1, row2);
std::cout << "Best candidate found results in " << number << " steps:\n";
verify(steps, row1, row2, true);
}
}
输出：
Best candidate found results in 8 steps:
Start verify
after 'toggle both 2':
row1: 00000000000000000000000000000100
row2: 00000000000000000000000000000100
after 'toggle both 4':
row1: 00000000000000000000000000010100
row2: 00000000000000000000000000010100
after 'toggle first from 1 through 5':
row1: 00000000000000000000000000101010
row2: 00000000000000000000000000010100
after 'toggle first from 9 through 12':
row1: 00000000000000000001111000101010
row2: 00000000000000000000000000010100
after 'toggle first from 14 through 15':
row1: 00000000000000001101111000101010
row2: 00000000000000000000000000010100
after 'toggle first from 17 through 19':
row1: 00000000000011101101111000101010
row2: 00000000000000000000000000010100
after 'toggle second from 11 through 12':
row1: 00000000000011101101111000101010
row2: 00000000000000000001100000010100
after 'toggle second from 14 through 18':
row1: 00000000000011101101111000101010
row2: 00000000000001111101100000010100
Done
#define BOOST_SPIRIT_USE_PHOENIX_V3
#include <boost/dynamic_bitset.hpp>
#include <iostream>
#include <sstream>
using bitset = boost::dynamic_bitset<>;
// bitset helpers
int count_ranges(bitset const& bs);
std::vector<bitset> combinations(bitset const& bs);
// generate the steps script
int emit_apply_both (std::ostream& os, bitset const& edits);
int emit_toggles (std::ostream& os, bitset const& row, std::string const& row_name);
int emit_steps (std::ostream& os, bitset const& row1, bitset const& row2, bitset const& edits);
// applies a steps script from scratch and verifies the result
// (optionally tracing all steps along the way)
bool verify(std::istream& is, bitset const& target1, bitset const& target2, bool verbose);
////////////////////////////////////////////////////
// The solver with a single, simple heuristic:
//
// If there's a hole in a range for row1 where row2 is to have a `1`, we might
// benefit from toggling both rows in advance, because it might result in a
// longer stretch to toggle in the first row
//
// An obvious improvement would to be to try with rows swapped as well.
//
// (As a bonus, all solutions are verified)
int solve(std::ostream& os, bitset row1, bitset row2)
{
auto candidates = row2 & ~row1;
int best_count = row1.size() + 1; // or INT_MAX or similar
bitset best_edits;
for (auto const& edits : combinations(candidates))
{
std::stringstream steps_stream;
int count = emit_steps(steps_stream, row1, row2, edits);
assert(verify(steps_stream, row1, row2, false));
if (count < best_count)
{
best_edits = edits;
best_count = count;
}
}
return emit_steps(os, row1, row2, best_edits);
}
// test driver reading the target configuration from stdin
// and displaying the 'best found' solution with intermediate steps
int main()
{
bitset row1, row2;
if (std::cin >> row1 >> row2)
{
std::stringstream steps;
int number = solve(steps, row1, row2);
std::cout << "Best candidate found results in " << number << " steps:\n";
verify(steps, row1, row2, true);
}
}
////////////////////////////////////////////////////
/// details, helpers
int count_ranges(bitset const& bs)
{
int count = 0;
for (auto bit=bs.find_first(); bit!=bitset::npos; bit=bs.find_next(bit))
{
do ++bit; while (bit<=bs.size() && bs[bit]);
++count;
}
return count;
}
std::vector<bitset> combinations(bitset const& bs)
{
bitset accum(bs.size());
std::vector<bitset> result;
std::function<void(size_t bit)> recurse = [&](size_t bit) mutable
{
if (bit == bitset::npos)
result.push_back(accum);
else
{
accum.flip(bit); recurse(bs.find_next(bit));
accum.flip(bit); recurse(bs.find_next(bit));
}
};
return recurse(bs.find_first()), result;
}
int emit_toggles(std::ostream& os, bitset const& row, std::string const& row_name)
{
int count = 0;
for (auto start=row.find_first(); start!=bitset::npos; start=row.find_next(start))
{
auto end = start;
do ++end; while (end<row.size() && row[end]);
if (start+1 == end)
os << "toggle " << row_name << " " << start << "\n";
else
os << "toggle " << row_name << " from " << start << " through " << (end-1) << "\n";
count += 1;
start = end;
}
return count;
}
int emit_apply_both(std::ostream& os, bitset const& edits)
{
for (auto bit=edits.find_first(); bit!=bitset::npos; bit=edits.find_next(bit))
os << "toggle both " << bit << "\n";
return edits.count();
}
int emit_steps(std::ostream& os, bitset const& row1, bitset const& row2, bitset const& edits)
{
auto count = emit_apply_both(os, edits);
count += emit_toggles (os, row1 ^ edits, "first");
count += emit_toggles (os, row2 ^ edits, "second");
return count;
}
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
template <typename Lambda> struct WrapAction {
template <typename...> struct result { typedef void type; };
template <typename... T> void operator()(T&&... t) const { _ll(std::forward<T>(t)...); }
WrapAction(Lambda&& ll) : _ll(std::forward<Lambda>(ll)) { }
private:
mutable Lambda _ll;
};
template <typename Lambda> WrapAction<Lambda> make_action(Lambda&& ll) { return { std::forward<Lambda>(ll) }; }
bool verify(std::istream& is, bitset const& target1, bitset const& target2, bool verbose)
{
bitset row1(target1.size()), row2(target2.size());
if (verbose) std::cout << "Start verify\n";
auto toggle1 = make_action([&](int i) mutable { row1.flip(i); });
auto toggle2 = make_action([&](int i) mutable { row2.flip(i); });
auto both = make_action([&](int i) mutable { toggle1(i); toggle2(i); });
auto range1 = make_action([&](int i1, int i2) mutable { while (i2>=i1) toggle1(i2--); });
auto range2 = make_action([&](int i1, int i2) mutable { while (i2>=i1) toggle2(i2--); });
// for statement tracing:
typedef boost::spirit::istream_iterator It;
auto trace = make_action([&](boost::iterator_range<It> const& raw_iterators) mutable {
if (verbose) {
std::cout << "after '" << std::string(raw_iterators.begin(), raw_iterators.end()) << "':\n";
std::cout << " row1:\t" << row1 << "\n" << " row2:\t" << row2 << "\n";
}
});
using namespace boost::spirit::qi;
namespace phx = boost::phoenix;
using phx::bind;
using phx::construct;
is.unsetf(std::ios::skipws);
It f(is), l;
bool ok = phrase_parse(f, l,
- raw [
lit("toggle") >> ("both" >> int_) [ bind(both, _1) ]
| lit("toggle") >> lit("first") >> ("from" >> int_ >> "through" >> int_) [ bind(range1, _1, _2) ]
| lit("toggle") >> lit("second") >> ("from" >> int_ >> "through" >> int_) [ bind(range2, _1, _2) ]
| "toggle" >> lit("first") >> (int_) [ bind(toggle1, _1) ]
| "toggle" >> lit("second") >> (int_) [ bind(toggle2, _1) ]
| eps(false)
] [ bind(trace, _1) ] % eol,
blank);
if (verbose)
{
if (ok) std::cout << "Done\n";
else std::cout << "Failed\n";
if (f != l) std::cout << "Remaining unparsed: '" << std::string(f,l) << "'\n";
}
return ok && (f==l) && (row1==target1) && (row2==target2);
}
最后，重新打开。是时候发布我的答案了：）
此解决方案使用单次迭代，只需7 个步骤O(n+1)即可解决 2x20 灯示例
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <cassert>
#include <functional>
using namespace std;
const string upperInput("11101101111000101010");
const string lowerInput("01111101100000010100");
vector<bool> upper, lower;
void init()
{ // convert string rows to vector<bool> rows
for_each(upperInput.begin(), upperInput.end(), [&](char e) { upper.push_back(e == '1'); });
for_each(lowerInput.begin(), lowerInput.end(), [&](char e) { lower.push_back(e == '1'); });
assert(upper.size() == lower.size());
}
void dump()
{ // output current content of vector<bool> rows
for_each(upper.begin(), upper.end(), [] (bool b) { cout << (b ? '1' : '0'); });
cout << endl;
for_each(lower.begin(), lower.end(), [] (bool b) { cout << (b ? '1' : '0'); });
cout << endl;
cout << endl;
}
// iterate over both rows with callback
typedef function<void (const vector<bool>::iterator& itUpper, const vector<bool>::iterator& itLower)> IteratorCallback;
void iterate(const bool includeEnd, const IteratorCallback callback)
{
for (auto itUpper = upper.begin(), itLower = lower.begin(); itUpper != upper.end(); itUpper++, itLower++)
callback(itUpper, itLower);
if (includeEnd)
callback(upper.end(), lower.end());
}
int main()
{
init();
cout << "Initial rows data: " << endl;
dump();
int steps = 0;
// a state is isolated if the state before and after holds the opposite value or is an isolated 1 at the beginning or end.
const auto isIsolatedState = [] (const vector<bool>& source, const vector<bool>::iterator& it) {
return (it != source.begin() && it != source.end() && *(it - 1) != *it && *(it + 1) != *it)
|| (it == source.begin() && *it && !*(it + 1))
|| (it == source.end() && *it && !*(it - 1));
};
// toggle consecutive states in the given range
const auto toggle = [] (const vector<bool>::iterator& begin, const vector<bool>::iterator& end)
{
for (auto it = begin; it != end; it++)
*it = !*it;
};
auto upperBlockStart = upper.front() ? upper.begin() : upper.end();
auto lowerBlockStart = lower.front() ? lower.begin() : lower.end();
iterate(true, [&upperBlockStart, &lowerBlockStart, &steps, isIsolatedState, toggle] (const vector<bool>::iterator& itUpper, const vector<bool>::iterator& itLower) {
// toggle columns if state in both rows is isolated
if (itUpper != upper.end())
{
const int column = itUpper - upper.begin() + 1;
if (isIsolatedState(upper, itUpper) && isIsolatedState(lower, itLower))
{
cout << "#" << ++steps << ": Toggling column " << column << endl;
toggle(itUpper, itUpper + 1);
toggle(itLower, itLower + 1);
dump();
}
}
// keep track of blocks with 1's in upper row
const bool upperState = itUpper != upper.end() ? *itUpper : false;
if (upperState && upperBlockStart == upper.end())
upperBlockStart = itUpper; // start of block of 1's in upper row
if (!upperState && upperBlockStart != upper.end())
{ // end of block of 1's in upper row
const int count = itUpper - upperBlockStart;
const int column = upperBlockStart - upper.begin() + 1;
cout << "#" << ++steps << ": Toggling " << count << " lamp(s) in upper row starting from column " << column << endl;
toggle(upperBlockStart, itUpper);
upperBlockStart = upper.end();
dump();
}
// keep track of blocks with 1's in lower row
const bool lowerState = itLower != lower.end() ? *itLower : false;
if (lowerState && *itLower && lowerBlockStart == lower.end())
lowerBlockStart = itLower; // start of block of 1's in lower row
if (!lowerState && lowerBlockStart != lower.end())
{ // end of block of 1's in lower row
const int count = itLower - lowerBlockStart;
const int column = lowerBlockStart - lower.begin() + 1;
cout << "#" << ++steps << ": Toggling " << count << " lamp(s) in lower row starting from column " << column << endl;
toggle(lowerBlockStart, itLower);
lowerBlockStart = lower.end();
dump();
}
});
cout << "Solved in " << steps << " step(s)" << endl;
return 0;
}
这是我的解决方案。O( N) 时间，单次通过。（甚至可以适应 O(1) 存储，如果您将输入格式更改为一次接受一列。）添加评论并证明其正确性是读者的练习。
#include <cstdlib>
#include <iostream>
#include <vector>
#include <array>
int main()
{
std::array<std::vector<bool>, 2> lamps;
auto row_iter = lamps.begin();
char c;
while (std::cin.get(c) && row_iter != lamps.end()) {
switch (c){
case '0':
row_iter->push_back(false);
break;
case '1':
row_iter->push_back(true);
break;
case '\n':
++row_iter;
break;
default:
std::cerr << "Unexpected input char "
<< static_cast<int>(c) << std::endl;
return EXIT_FAILURE;
}
}
std::vector<bool>& row1 = lamps[0];
std::vector<bool>& row2 = lamps[1];
if (row1.size() != row2.size()) {
std::cerr << "Rows must be the same length" << std::endl;
return EXIT_FAILURE;
}
row1.push_back(false);
row2.push_back(false);
unsigned int col_flips = 0;
unsigned int changes = 0;
bool prev1 = false, prev2 = false, both_changed = false;
for (auto iter1=row1.cbegin(), iter2=row2.cbegin();
iter1 != row1.cend() && iter2 != row2.cend();
++iter1, ++iter2) {
unsigned int col_changes = (*iter1 != prev1);
col_changes += (*iter2 != prev2);
if (col_changes == 2) {
if (both_changed) {
changes -= 2;
++col_flips;
both_changed = false;
} else {
changes += col_changes;
both_changed = true;
}
} else {
changes += col_changes;
both_changed = false;
}
prev1 = *iter1;
prev2 = *iter2;
}
std::cout << col_flips + changes/2 << std::endl;
return EXIT_SUCCESS;
}