[已解决]通过穷举找到正确的解答方案！

饭-米粒

目的：想通过程序解决如下问题！将全部灯泡点亮。
0     1                                       
1     0               
1     1                                          
0     1                                       
代表8个灯泡，（1---亮，0---灭）如何将他们全部点亮。
规则：点击一个灯泡，他所在列的灯泡全部取反，另一列与之同行的灯泡状态也取反；（点一下，有5个灯泡改变状态）；
各位大佬们有没有什么好办法!

最佳答案

月排行榜 / 总排行榜

Croper

2019-10-26 05:21:32

之前练习时写了个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[0].size(),blub(this)));
                for (int i = 0; i < base.size(); ++i) {
                        for (int j = 0; j < base[i].size(); ++j) {
                                if (base[i][j]) {
                                        _grid[i][j].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[i].size(); ++j) {
                                _grid[i][j]._master = this;
                        }
                }
        }
        size_t width() const {
                if (_grid.size() == 0) return 0;
                return _grid[0].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[y].size()) {
                        return;
                }

                _grid[y][x].toggle();
                if (y - 1 >= 0) _grid[y - 1][x].toggle();
                if (y + 1 < _grid.size()) _grid[y + 1][x].toggle();
                if (x - 1 >= 0) _grid[y][x - 1].toggle();
                if (x + 1 < _grid[y].size()) _grid[y][x + 1].toggle();
        }
        */
        void toggle(int y, int x) {  //切换坐标为（x,y)的灯泡以及与其相同行列的灯泡的状态
                if (y < 0 || y >= _grid.size() || x < 0 || x >= _grid[y].size()) {
                        return;
                }
                for (int x1 = 0; x1 < _grid[y].size(); ++x1) {
                        _grid[y][x1].toggle();
                }
                for (int y1 = 0; y1 < _grid.size(); ++y1) {
                        _grid[y1][x].toggle();
                }
                _grid[y][x].toggle();
        }

        int clightblub() const{  //返回亮的灯泡的数目
                return _clightblub;
        }

        bool Alllight() const {  //是否所有灯泡都亮了
                return _clightblub == _grid.size()*_grid[0].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[y].size(); ++x) {
                                ret = ret * 31 + grid[y][x];
                        }
                }
                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[0].size() != grid2[0].size()) {
                        return grid1[0].size() < grid2[0].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[i].size(); ++j) {
                                if (grid1[i][j] != grid2[i][j]) {
                                        return grid1[i][j] < grid2[i][j];
                                }
                        }
                }
                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[q] = 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[b] == 0) {
                                        path[b] = path[q];
                                        bool duplicate = false;  
                                        for (int k = 0; k < path[b].size(); ++k) {
                                                if (path[b][k] == pair<int, int>(i, j)) {
                                                        path[b].erase(path[b].begin() + k);
                                                        duplicate = true;
                                                        break;
                                                }
                                        }
                                        if (!duplicate) {
                                                path[b].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[q];
}

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[i].first << "," << a[i].second << endl;
        }
        system("pause");
}

得到答案

3，1
1，0
0，1
3，0

跳转到最佳答案楼层

Croper

之前练习时写了个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[0].size(),blub(this)));
                for (int i = 0; i < base.size(); ++i) {
                        for (int j = 0; j < base[i].size(); ++j) {
                                if (base[i][j]) {
                                        _grid[i][j].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[i].size(); ++j) {
                                _grid[i][j]._master = this;
                        }
                }
        }
        size_t width() const {
                if (_grid.size() == 0) return 0;
                return _grid[0].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[y].size()) {
                        return;
                }

                _grid[y][x].toggle();
                if (y - 1 >= 0) _grid[y - 1][x].toggle();
                if (y + 1 < _grid.size()) _grid[y + 1][x].toggle();
                if (x - 1 >= 0) _grid[y][x - 1].toggle();
                if (x + 1 < _grid[y].size()) _grid[y][x + 1].toggle();
        }
        */
        void toggle(int y, int x) {  //切换坐标为（x,y)的灯泡以及与其相同行列的灯泡的状态
                if (y < 0 || y >= _grid.size() || x < 0 || x >= _grid[y].size()) {
                        return;
                }
                for (int x1 = 0; x1 < _grid[y].size(); ++x1) {
                        _grid[y][x1].toggle();
                }
                for (int y1 = 0; y1 < _grid.size(); ++y1) {
                        _grid[y1][x].toggle();
                }
                _grid[y][x].toggle();
        }

        int clightblub() const{  //返回亮的灯泡的数目
                return _clightblub;
        }

        bool Alllight() const {  //是否所有灯泡都亮了
                return _clightblub == _grid.size()*_grid[0].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[y].size(); ++x) {
                                ret = ret * 31 + grid[y][x];
                        }
                }
                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[0].size() != grid2[0].size()) {
                        return grid1[0].size() < grid2[0].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[i].size(); ++j) {
                                if (grid1[i][j] != grid2[i][j]) {
                                        return grid1[i][j] < grid2[i][j];
                                }
                        }
                }
                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[q] = 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[b] == 0) {
                                        path[b] = path[q];
                                        bool duplicate = false;  
                                        for (int k = 0; k < path[b].size(); ++k) {
                                                if (path[b][k] == pair<int, int>(i, j)) {
                                                        path[b].erase(path[b].begin() + k);
                                                        duplicate = true;
                                                        break;
                                                }
                                        }
                                        if (!duplicate) {
                                                path[b].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[q];
}

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[i].first << "," << a[i].second << endl;
        }
        system("pause");
}

得到答案

3，1
1，0
0，1
3，0

饭-米粒

Croper 发表于 2019-10-26 05:21
之前练习时写了个A星算法解决开灯游戏的，改了一下toggle函数应该能符合你的要求
得到答案

大佬辛苦了！