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

饭-米粒

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

最佳答案

月排行榜 / 总排行榜

Croper

2019-10-26 05:21:32

之前练习时写了个A星算法解决开灯游戏的，改了一下toggle函数应该能符合你的要求

1. #include <iostream>
   
2. #include <vector>
   
3. #include <utility>
   
4. #include <unordered_map>
   
5. #include <set>
   
6. #include <string>
   
7. using namespace std;
   
8. 
   
9. //灯泡类
   
10. //储存单个灯泡的状态，使用toggle切换状态
    
11. 
    
12. class board;
    
13. 
    
14. class blub {
    
15. friend class board;
    
16. private:
    
17.         int _state;     //当前状态，0为关闭，1为开启
    
18.         board* _master; //指向处于的墙
    
19. public:
    
20.         blub(board* master=0) :_state(0),_master(master) {};
    
21. 
    
22.         int toggle();    //切换状态，返回切换后的状态
    
23. 
    
24.         operator int() const {
    
25.                 return _state;
    
26.         }
    
27. };
    
28. 
    
29. //墙类
    
30. //墙上有X*Y个灯泡
    
31. class board {
    
32. friend class blub;
    
33. friend class board_hash;
    
34. friend class board_equal;
    
35. friend class board_cmp;
    
36. private:
    
37.         vector<vector<blub>> _grid;  //存储墙上所有灯泡
    
38.         int _clightblub;             //记录发亮的灯泡数目
    
39. public:
    
40. 
    
41.         board(vector<vector<int>> base) {
    
42.                 _clightblub = 0;
    
43.                 _grid.resize(base.size(), vector<blub>(base[0].size(),blub(this)));
    
44.                 for (int i = 0; i < base.size(); ++i) {
    
45.                         for (int j = 0; j < base[i].size(); ++j) {
    
46.                                 if (base[i][j]) {
    
47.                                         _grid[i][j].toggle();
    
48.                                 }
    
49.                         }
    
50.                 }
    
51.         }
    
52. 
    
53.         board(const board& origin) {
    
54.                 _grid = origin._grid;
    
55.                 _clightblub = origin._clightblub;
    
56.                 for (int i = 0; i < _grid.size(); ++i) {
    
57.                         for (int j = 0; j < _grid[i].size(); ++j) {
    
58.                                 _grid[i][j]._master = this;
    
59.                         }
    
60.                 }
    
61.         }
    
62.         size_t width() const {
    
63.                 if (_grid.size() == 0) return 0;
    
64.                 return _grid[0].size();
    
65.         }
    
66. 
    
67.         size_t height() const {
    
68.                 return _grid.size();
    
69.         }
    
70. 
    
71.         /*
    
72.         void toggle(int y, int x) {  //切换坐标为（x,y)的灯泡以及相邻灯泡的状态
    
73.                 if (y < 0 || y >= _grid.size() || x < 0 || x >= _grid[y].size()) {
    
74.                         return;
    
75.                 }
    
76. 
    
77.                 _grid[y][x].toggle();
    
78.                 if (y - 1 >= 0) _grid[y - 1][x].toggle();
    
79.                 if (y + 1 < _grid.size()) _grid[y + 1][x].toggle();
    
80.                 if (x - 1 >= 0) _grid[y][x - 1].toggle();
    
81.                 if (x + 1 < _grid[y].size()) _grid[y][x + 1].toggle();
    
82.         }
    
83.         */
    
84.         void toggle(int y, int x) {  //切换坐标为（x,y)的灯泡以及与其相同行列的灯泡的状态
    
85.                 if (y < 0 || y >= _grid.size() || x < 0 || x >= _grid[y].size()) {
    
86.                         return;
    
87.                 }
    
88.                 for (int x1 = 0; x1 < _grid[y].size(); ++x1) {
    
89.                         _grid[y][x1].toggle();
    
90.                 }
    
91.                 for (int y1 = 0; y1 < _grid.size(); ++y1) {
    
92.                         _grid[y1][x].toggle();
    
93.                 }
    
94.                 _grid[y][x].toggle();
    
95.         }
    
96. 
    
97.         int clightblub() const{  //返回亮的灯泡的数目
    
98.                 return _clightblub;
    
99.         }
    
100. 
     
101.         bool Alllight() const {  //是否所有灯泡都亮了
     
102.                 return _clightblub == _grid.size()*_grid[0].size();
     
103.         }
     
104. };
     
105. 
     
106. int blub::toggle() {      //切换状态，返回切换后的状态
     
107.         _state = 1 - _state;
     
108.         if (_master != 0) {
     
109.                 _master->_clightblub += (_state ? 1 : -1);
     
110.         }
     
111.         return _state;
     
112. }
     
113. class board_hash {  //网上抄的hashcode计算方法
     
114. public:
     
115.         size_t operator()(const board& b) const {
     
116.                 const vector<vector<blub>>& grid = b._grid;
     
117.                 size_t ret = 17;
     
118.                 for (int y=0;y<grid.size();++y){
     
119.                         for (int x = 0; x < grid[y].size(); ++x) {
     
120.                                 ret = ret * 31 + grid[y][x];
     
121.                         }
     
122.                 }
     
123.                 return ret;
     
124.         }
     
125. };
     
126. 
     
127. class board_equal {
     
128. public:
     
129.         bool operator()(const board& b1, const board& b2) const {
     
130.                 bool b= b1._grid == b2._grid;
     
131.                 return b1._grid == b2._grid;
     
132.         }
     
133. };
     
134. 
     
135. class board_cmp {
     
136. public:
     
137.         bool operator()(const board& b1, const board& b2) const {
     
138.                 if (b1._grid.size() == 0 && b2._grid.size() == 0) {
     
139.                         return false;
     
140.                 }
     
141.                 const vector<vector<blub>>& grid1 = b1._grid;
     
142.                 const vector<vector<blub>>& grid2 = b2._grid;
     
143.                 if (grid1.size() != grid2.size()) {
     
144.                         return grid1.size() < grid2.size();
     
145.                 }
     
146.                 if (grid1[0].size() != grid2[0].size()) {
     
147.                         return grid1[0].size() < grid2[0].size();
     
148.                 }
     
149.                 if (b1.clightblub() != b2.clightblub()) {
     
150.                         return b1.clightblub() > b2.clightblub();
     
151.                 }
     
152.                 for (int i = 0; i < grid1.size(); ++i) {
     
153.                         for (int j = 0; j < grid1[i].size(); ++j) {
     
154.                                 if (grid1[i][j] != grid2[i][j]) {
     
155.                                         return grid1[i][j] < grid2[i][j];
     
156.                                 }
     
157.                         }
     
158.                 }
     
159.                 return false;
     
160.         }
     
161. };
     
162. 
     
163. vector<pair<int, int>> findway(board q) {
     
164.         unordered_map<board, int,board_hash,board_equal> close_map;//当值为1时说明其已不需要关注
     
165.         set<board, board_cmp> openlist;
     
166.         unordered_map<board, vector<pair<int, int>>, board_hash, board_equal> path;
     
167.         int n = 0;
     
168.         while (!q.Alllight()) {
     
169.                 close_map[q] = 1;
     
170.                 for (int i = 0; i < q.height(); ++i) {
     
171.                         for (int j = 0; j < q.width(); ++j) {
     
172.                                 board b = q;
     
173.                                 b.toggle(i, j);
     
174.                                 n++;
     
175.                                 if (close_map[b] == 0) {
     
176.                                         path[b] = path[q];
     
177.                                         bool duplicate = false;  
     
178.                                         for (int k = 0; k < path[b].size(); ++k) {
     
179.                                                 if (path[b][k] == pair<int, int>(i, j)) {
     
180.                                                         path[b].erase(path[b].begin() + k);
     
181.                                                         duplicate = true;
     
182.                                                         break;
     
183.                                                 }
     
184.                                         }
     
185.                                         if (!duplicate) {
     
186.                                                 path[b].push_back({ i,j });
     
187.                                         }
     
188.                                         openlist.insert(b);
     
189.                                 }
     
190.                         }
     
191.                 }
     
192.                 if (n>200000 || openlist.empty()) {
     
193.                         return { {-1,-1} };
     
194.                 }
     
195.                 q = std::move(*openlist.begin());
     
196.                 openlist.erase(openlist.begin());
     
197.         }
     
198.         return path[q];
     
199. }
     
200. 
     
201. int main() {
     
202.         board q = vector<vector<int>>({
     
203.         {0,1},
     
204.         {1,0},
     
205.         {1,1},
     
206.         {0,0},
     
207.         });
     
208. 
     
209.         auto a = findway(q);
     
210.         for (int i = 0; i < a.size(); ++i) {
     
211.                 cout << a[i].first << "," << a[i].second << endl;
     
212.         }
     
213.         system("pause");
     
214. }

复制代码

得到答案

1. 3，1
   
2. 1，0
   
3. 0，1
   
4. 3，0

复制代码

跳转到最佳答案楼层

Croper

之前练习时写了个A星算法解决开灯游戏的，改了一下toggle函数应该能符合你的要求

1. #include <iostream>
   
2. #include <vector>
   
3. #include <utility>
   
4. #include <unordered_map>
   
5. #include <set>
   
6. #include <string>
   
7. using namespace std;
   
8. 
   
9. //灯泡类
   
10. //储存单个灯泡的状态，使用toggle切换状态
    
11. 
    
12. class board;
    
13. 
    
14. class blub {
    
15. friend class board;
    
16. private:
    
17.         int _state;     //当前状态，0为关闭，1为开启
    
18.         board* _master; //指向处于的墙
    
19. public:
    
20.         blub(board* master=0) :_state(0),_master(master) {};
    
21. 
    
22.         int toggle();    //切换状态，返回切换后的状态
    
23. 
    
24.         operator int() const {
    
25.                 return _state;
    
26.         }
    
27. };
    
28. 
    
29. //墙类
    
30. //墙上有X*Y个灯泡
    
31. class board {
    
32. friend class blub;
    
33. friend class board_hash;
    
34. friend class board_equal;
    
35. friend class board_cmp;
    
36. private:
    
37.         vector<vector<blub>> _grid;  //存储墙上所有灯泡
    
38.         int _clightblub;             //记录发亮的灯泡数目
    
39. public:
    
40. 
    
41.         board(vector<vector<int>> base) {
    
42.                 _clightblub = 0;
    
43.                 _grid.resize(base.size(), vector<blub>(base[0].size(),blub(this)));
    
44.                 for (int i = 0; i < base.size(); ++i) {
    
45.                         for (int j = 0; j < base[i].size(); ++j) {
    
46.                                 if (base[i][j]) {
    
47.                                         _grid[i][j].toggle();
    
48.                                 }
    
49.                         }
    
50.                 }
    
51.         }
    
52. 
    
53.         board(const board& origin) {
    
54.                 _grid = origin._grid;
    
55.                 _clightblub = origin._clightblub;
    
56.                 for (int i = 0; i < _grid.size(); ++i) {
    
57.                         for (int j = 0; j < _grid[i].size(); ++j) {
    
58.                                 _grid[i][j]._master = this;
    
59.                         }
    
60.                 }
    
61.         }
    
62.         size_t width() const {
    
63.                 if (_grid.size() == 0) return 0;
    
64.                 return _grid[0].size();
    
65.         }
    
66. 
    
67.         size_t height() const {
    
68.                 return _grid.size();
    
69.         }
    
70. 
    
71.         /*
    
72.         void toggle(int y, int x) {  //切换坐标为（x,y)的灯泡以及相邻灯泡的状态
    
73.                 if (y < 0 || y >= _grid.size() || x < 0 || x >= _grid[y].size()) {
    
74.                         return;
    
75.                 }
    
76. 
    
77.                 _grid[y][x].toggle();
    
78.                 if (y - 1 >= 0) _grid[y - 1][x].toggle();
    
79.                 if (y + 1 < _grid.size()) _grid[y + 1][x].toggle();
    
80.                 if (x - 1 >= 0) _grid[y][x - 1].toggle();
    
81.                 if (x + 1 < _grid[y].size()) _grid[y][x + 1].toggle();
    
82.         }
    
83.         */
    
84.         void toggle(int y, int x) {  //切换坐标为（x,y)的灯泡以及与其相同行列的灯泡的状态
    
85.                 if (y < 0 || y >= _grid.size() || x < 0 || x >= _grid[y].size()) {
    
86.                         return;
    
87.                 }
    
88.                 for (int x1 = 0; x1 < _grid[y].size(); ++x1) {
    
89.                         _grid[y][x1].toggle();
    
90.                 }
    
91.                 for (int y1 = 0; y1 < _grid.size(); ++y1) {
    
92.                         _grid[y1][x].toggle();
    
93.                 }
    
94.                 _grid[y][x].toggle();
    
95.         }
    
96. 
    
97.         int clightblub() const{  //返回亮的灯泡的数目
    
98.                 return _clightblub;
    
99.         }
    
100. 
     
101.         bool Alllight() const {  //是否所有灯泡都亮了
     
102.                 return _clightblub == _grid.size()*_grid[0].size();
     
103.         }
     
104. };
     
105. 
     
106. int blub::toggle() {      //切换状态，返回切换后的状态
     
107.         _state = 1 - _state;
     
108.         if (_master != 0) {
     
109.                 _master->_clightblub += (_state ? 1 : -1);
     
110.         }
     
111.         return _state;
     
112. }
     
113. class board_hash {  //网上抄的hashcode计算方法
     
114. public:
     
115.         size_t operator()(const board& b) const {
     
116.                 const vector<vector<blub>>& grid = b._grid;
     
117.                 size_t ret = 17;
     
118.                 for (int y=0;y<grid.size();++y){
     
119.                         for (int x = 0; x < grid[y].size(); ++x) {
     
120.                                 ret = ret * 31 + grid[y][x];
     
121.                         }
     
122.                 }
     
123.                 return ret;
     
124.         }
     
125. };
     
126. 
     
127. class board_equal {
     
128. public:
     
129.         bool operator()(const board& b1, const board& b2) const {
     
130.                 bool b= b1._grid == b2._grid;
     
131.                 return b1._grid == b2._grid;
     
132.         }
     
133. };
     
134. 
     
135. class board_cmp {
     
136. public:
     
137.         bool operator()(const board& b1, const board& b2) const {
     
138.                 if (b1._grid.size() == 0 && b2._grid.size() == 0) {
     
139.                         return false;
     
140.                 }
     
141.                 const vector<vector<blub>>& grid1 = b1._grid;
     
142.                 const vector<vector<blub>>& grid2 = b2._grid;
     
143.                 if (grid1.size() != grid2.size()) {
     
144.                         return grid1.size() < grid2.size();
     
145.                 }
     
146.                 if (grid1[0].size() != grid2[0].size()) {
     
147.                         return grid1[0].size() < grid2[0].size();
     
148.                 }
     
149.                 if (b1.clightblub() != b2.clightblub()) {
     
150.                         return b1.clightblub() > b2.clightblub();
     
151.                 }
     
152.                 for (int i = 0; i < grid1.size(); ++i) {
     
153.                         for (int j = 0; j < grid1[i].size(); ++j) {
     
154.                                 if (grid1[i][j] != grid2[i][j]) {
     
155.                                         return grid1[i][j] < grid2[i][j];
     
156.                                 }
     
157.                         }
     
158.                 }
     
159.                 return false;
     
160.         }
     
161. };
     
162. 
     
163. vector<pair<int, int>> findway(board q) {
     
164.         unordered_map<board, int,board_hash,board_equal> close_map;//当值为1时说明其已不需要关注
     
165.         set<board, board_cmp> openlist;
     
166.         unordered_map<board, vector<pair<int, int>>, board_hash, board_equal> path;
     
167.         int n = 0;
     
168.         while (!q.Alllight()) {
     
169.                 close_map[q] = 1;
     
170.                 for (int i = 0; i < q.height(); ++i) {
     
171.                         for (int j = 0; j < q.width(); ++j) {
     
172.                                 board b = q;
     
173.                                 b.toggle(i, j);
     
174.                                 n++;
     
175.                                 if (close_map[b] == 0) {
     
176.                                         path[b] = path[q];
     
177.                                         bool duplicate = false;  
     
178.                                         for (int k = 0; k < path[b].size(); ++k) {
     
179.                                                 if (path[b][k] == pair<int, int>(i, j)) {
     
180.                                                         path[b].erase(path[b].begin() + k);
     
181.                                                         duplicate = true;
     
182.                                                         break;
     
183.                                                 }
     
184.                                         }
     
185.                                         if (!duplicate) {
     
186.                                                 path[b].push_back({ i,j });
     
187.                                         }
     
188.                                         openlist.insert(b);
     
189.                                 }
     
190.                         }
     
191.                 }
     
192.                 if (n>200000 || openlist.empty()) {
     
193.                         return { {-1,-1} };
     
194.                 }
     
195.                 q = std::move(*openlist.begin());
     
196.                 openlist.erase(openlist.begin());
     
197.         }
     
198.         return path[q];
     
199. }
     
200. 
     
201. int main() {
     
202.         board q = vector<vector<int>>({
     
203.         {0,1},
     
204.         {1,0},
     
205.         {1,1},
     
206.         {0,0},
     
207.         });
     
208. 
     
209.         auto a = findway(q);
     
210.         for (int i = 0; i < a.size(); ++i) {
     
211.                 cout << a[i].first << "," << a[i].second << endl;
     
212.         }
     
213.         system("pause");
     
214. }

复制代码

得到答案

1. 3，1
   
2. 1，0
   
3. 0，1
   
4. 3，0

复制代码

饭-米粒

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

大佬辛苦了！