通过穷举找到正确的解答方案！
目的：想通过程序解决如下问题！将全部灯泡点亮。0 1
1 0
1 1
0 1
代表8个灯泡，（1---亮，0---灭）如何将他们全部点亮。
规则：点击一个灯泡，他所在列的灯泡全部取反，另一列与之同行的灯泡状态也取反；（点一下，有5个灯泡改变状态）；
各位大佬们有没有什么好办法!
本帖最后由 Croper 于 2019-10-26 05:24 编辑
之前练习时写了个A星算法解决开灯游戏的，改了一下toggle函数应该能符合你的要求#include <iostream>
#include <vector>
#include <utility>
#include <unordered_map>
#include <set>
#include <string>
using namespace std;
//灯泡类
//储存单个灯泡的状态，使用toggle切换状态
class board;
class blub {
friend class board;
private:
int _state; //当前状态，0为关闭，1为开启
board* _master; //指向处于的墙
public:
blub(board* master=0) :_state(0),_master(master) {};
int toggle(); //切换状态，返回切换后的状态
operator int() const {
return _state;
}
};
//墙类
//墙上有X*Y个灯泡
class board {
friend class blub;
friend class board_hash;
friend class board_equal;
friend class board_cmp;
private:
vector<vector<blub>> _grid;//存储墙上所有灯泡
int _clightblub; //记录发亮的灯泡数目
public:
board(vector<vector<int>> base) {
_clightblub = 0;
_grid.resize(base.size(), vector<blub>(base.size(),blub(this)));
for (int i = 0; i < base.size(); ++i) {
for (int j = 0; j < base.size(); ++j) {
if (base) {
_grid.toggle();
}
}
}
}
board(const board& origin) {
_grid = origin._grid;
_clightblub = origin._clightblub;
for (int i = 0; i < _grid.size(); ++i) {
for (int j = 0; j < _grid.size(); ++j) {
_grid._master = this;
}
}
}
size_t width() const {
if (_grid.size() == 0) return 0;
return _grid.size();
}
size_t height() const {
return _grid.size();
}
/*
void toggle(int y, int x) {//切换坐标为（x,y)的灯泡以及相邻灯泡的状态
if (y < 0 || y >= _grid.size() || x < 0 || x >= _grid.size()) {
return;
}
_grid.toggle();
if (y - 1 >= 0) _grid.toggle();
if (y + 1 < _grid.size()) _grid.toggle();
if (x - 1 >= 0) _grid.toggle();
if (x + 1 < _grid.size()) _grid.toggle();
}
*/
void toggle(int y, int x) {//切换坐标为（x,y)的灯泡以及与其相同行列的灯泡的状态
if (y < 0 || y >= _grid.size() || x < 0 || x >= _grid.size()) {
return;
}
for (int x1 = 0; x1 < _grid.size(); ++x1) {
_grid.toggle();
}
for (int y1 = 0; y1 < _grid.size(); ++y1) {
_grid.toggle();
}
_grid.toggle();
}
int clightblub() const{//返回亮的灯泡的数目
return _clightblub;
}
bool Alllight() const {//是否所有灯泡都亮了
return _clightblub == _grid.size()*_grid.size();
}
};
int blub::toggle() { //切换状态，返回切换后的状态
_state = 1 - _state;
if (_master != 0) {
_master->_clightblub += (_state ? 1 : -1);
}
return _state;
}
class board_hash {//网上抄的hashcode计算方法
public:
size_t operator()(const board& b) const {
const vector<vector<blub>>& grid = b._grid;
size_t ret = 17;
for (int y=0;y<grid.size();++y){
for (int x = 0; x < grid.size(); ++x) {
ret = ret * 31 + grid;
}
}
return ret;
}
};
class board_equal {
public:
bool operator()(const board& b1, const board& b2) const {
bool b= b1._grid == b2._grid;
return b1._grid == b2._grid;
}
};
class board_cmp {
public:
bool operator()(const board& b1, const board& b2) const {
if (b1._grid.size() == 0 && b2._grid.size() == 0) {
return false;
}
const vector<vector<blub>>& grid1 = b1._grid;
const vector<vector<blub>>& grid2 = b2._grid;
if (grid1.size() != grid2.size()) {
return grid1.size() < grid2.size();
}
if (grid1.size() != grid2.size()) {
return grid1.size() < grid2.size();
}
if (b1.clightblub() != b2.clightblub()) {
return b1.clightblub() > b2.clightblub();
}
for (int i = 0; i < grid1.size(); ++i) {
for (int j = 0; j < grid1.size(); ++j) {
if (grid1 != grid2) {
return grid1 < grid2;
}
}
}
return false;
}
};
vector<pair<int, int>> findway(board q) {
unordered_map<board, int,board_hash,board_equal> close_map;//当值为1时说明其已不需要关注
set<board, board_cmp> openlist;
unordered_map<board, vector<pair<int, int>>, board_hash, board_equal> path;
int n = 0;
while (!q.Alllight()) {
close_map = 1;
for (int i = 0; i < q.height(); ++i) {
for (int j = 0; j < q.width(); ++j) {
board b = q;
b.toggle(i, j);
n++;
if (close_map == 0) {
path = path;
bool duplicate = false;
for (int k = 0; k < path.size(); ++k) {
if (path == pair<int, int>(i, j)) {
path.erase(path.begin() + k);
duplicate = true;
break;
}
}
if (!duplicate) {
path.push_back({ i,j });
}
openlist.insert(b);
}
}
}
if (n>200000 || openlist.empty()) {
return { {-1,-1} };
}
q = std::move(*openlist.begin());
openlist.erase(openlist.begin());
}
return path;
}
int main() {
board q = vector<vector<int>>({
{0,1},
{1,0},
{1,1},
{0,0},
});
auto a = findway(q);
for (int i = 0; i < a.size(); ++i) {
cout << a.first << "," << a.second << endl;
}
system("pause");
}
得到答案3，1
1，0
0，1
3，0 Croper 发表于 2019-10-26 05:21
之前练习时写了个A星算法解决开灯游戏的，改了一下toggle函数应该能符合你的要求
得到答案
大佬辛苦了！{:9_236:}
页:
[1]