请教一道算法题

给定一个二维数组，其中的1只可以变为0， 0只可以变为1 更改一个元素的时候，上下左右连同自己都会翻转。问最少几次可以翻转为全部都是1。感觉除了暴力没有什么思路，有其他解法吗？


case 1：output: 1
1011       1111
0001 ->  1111
1011      1111

翻转(1,1)

case 2: output: 4

1111       11OO       111O       1111       1111
1O11 - > 1O1O - >  11O1 - > 111O - > 1111
1111       1111        11O1       11OO      1111
  
依次翻转(0,3) -> (1,2) -> (3,2) -> (2,3)

暴力是暴力，但是可以稍微聪明一点的暴力。这个题目的话，bfs/dfs都可以做。bfs的话就是说直接从目标状态开始，然后bfs，算步数。中间需要一些hashing，把每个状态hash一下。bfs的话有一种优化的方法，就是用双向bfs（bidirectional bfs），大概可以优化到根号下原先bfs的时间复杂度，也是指数级别。
dfs的话，其实是可以比纯粹暴力优化一些的。枚举的顺序非常重要。不管怎么说，这个题目都是NP-complete问题，所以基本上枚举就是正解了。
dfs的话，可以通过控制搜索顺序来达到更好的时间复杂度（虽然不管怎么好都是exponential）。

更确切的说法其实是，这个A的逆叫做有限整数域Z_2意义下的逆。所谓有限整数域Z_2，就是说大于1的元素的操作不存在，我们认为 2=0， 1=-1
因为A是个方阵，这个逆总存在。

好像以前玩过一个类似的游戏，当时不知道是不是所有的组合都可以成功。

不过大概理解了意思，写了一下代码，不知道是不是所有的case都可以cover

欢迎讨论

1. 
   
2. [i]#include <iostream>
   
3. #include <string>
   
4. #include <vector>
   
5. #include <queue>
   
6. #include <unordered_map>
   
7. #include <unordered_set>
   
8. #include <algorithm>
   
9. using namespace std;
   
10. 
    
11. string flip(string input, int y, int x, int m, int n)
    
12. {
    
13.     auto change = [&](int i, int j)
    
14.     {
    
15.         if(i<0||i>=m||j<0||j>=n) return;
    
16.         input[i*n+j]= input[i*n+j]=='0'?'1':'0';
    
17.     };
    
18.     change(y,x);
    
19.     change(y+1,x);
    
20.     change(y-1,x);
    
21.     change(y,x+1);
    
22.     change(y,x-1);
    
23.     return input;
    
24. }
    
25. vector<string> findMoves(string input, int m, int n)
    
26. {
    
27.     string target(m*n, '1');
    
28.     if(target == input) return {input};
    
29.     queue<string> q;
    
30.     q.push(input);
    
31.     unordered_set<string> visited{input};
    
32.     unordered_map<string,string> path;
    
33. 
    
34.     while(!q.empty())
    
35.     {
    
36.         int size = q.size();
    
37.         while(size--)
    
38.         {
    
39.             string f = q.front(); q.pop();
    
40.             for(int i=0; i<m; ++i) for(int j=0;j<n; ++j)
    
41.             {
    
42.                 string next = flip(f,i,j,m,n);
    
43.                 if(next == target)
    
44.                 {
    
45.                     vector<string> res{target};
    
46.                     string str = f;
    
47.                     while(path.count(str))
    
48.                     {
    
49.                         res.push_back(str);
    
50.                         str = path[str];
    
51.                     }
    
52.                     res.push_back(input);
    
53.                     reverse(res.begin(), res.end());
    
54.                     return res;
    
55.                 }
    
56.                 if(visited.count(next)) continue;
    
57.                 visited.insert(next);
    
58.                 path[next] = f;
    
59.                 q.push(next);
    
60.                
    
61.             }
    
62.         }
    
63.     }
    
64.     return {};
    
65. }
    
66. int findMoves(vector<vector<int>> input)
    
67. {
    
68.     string str;
    
69.     for(int i=0;i<(int)input.size();++i) for(int j=0;j<(int)input[i].size();++j) str+=input[i][j]+'0';
    
70.     auto res = findMoves(str, (int)input.size(), (int)input[0].size());
    
71.     for(auto& i : res) cout << i << " ";
    
72.     cout << endl;
    
73.     return res.size()-1;
    
74. }
    
75. 
    
76. 
    
77. 
    
78. int main()
    
79. {
    
80.     vector<vector<int>> matrix{
    
81.         {1,1,1,1},
    
82.         {1,0,1,1},
    
83.         {1,1,1,1},
    
84.         };
    
85.     cout << findMoves(matrix) << endl;
    
86.     return 0;
    
87. }
    
88. [i][i]
    
89. [i]
    

复制代码

[/i][/i][/i][/i]

暴力是指？

这是算法题还是puzzle呀！

你可以把这道题当作解线性方程组，求解Ax=T。你需要有点线性代数的思维。
x是一个列向量，长度是m = axb，其中a，b是原矩形的维度。x的每一个元素表示棋盘的一个格子的动作（1表示翻转，0表示不翻转）
A是状态转移矩阵，维度是mxm，Ax的结果也是一个长度为m的列向量，表示原棋盘状态x经过指定的翻转操作后，得到的新棋盘状态。
A的元素可以通过规则定义来构造。
如果T是最终状态，那么x可以通过A的逆乘以T得到。注意x可能无解。另外x的解的每个元素可能大于1，翻转多余两次是没有意义的，需要再对x mod 2.

给了个3x3的解：

1. import numpy as np
   
2. A = np.array([
   
3.         [1,1,0,1,0,0,0,0,0],
   
4.         [1,1,1,0,1,0,0,0,0],
   
5.         [0,1,1,0,0,1,0,0,0],
   
6.         [1,0,0,1,1,0,1,0,0],
   
7.         [0,1,0,1,1,1,0,1,0],
   
8.         [0,0,1,0,1,1,0,0,1],
   
9.         [0,0,0,1,0,0,1,1,0],
   
10.         [0,0,0,0,1,0,1,1,1],
    
11.         [0,0,0,0,0,1,0,1,1]],'float')
    
12. A = np.transpose(A)
    
13. 
    
14. iA = np.linalg.inv(A)*7
    
15. iA.astype('int') % 2
    
16. 
    
17. S = np.array([[1,1,1,1,1,1,1,1,1]])
    
18. S = np.transpose(S)
    
19. T = np.array([[0,0,0,0,0,0,0,0,0]])
    
20. T = np.transpose(T)
    
21. 
    
22. ret = np.dot(iA,T-S)
    
23. ret = np.rint(ret)
    
24. ret = ret % 2
    
25. print(ret)

复制代码

顺便说一句，Ax=T的解可能有无数个。但通过x = A的伪逆乘以T 得到的解，是所有解中L2范数最小的，符合本题的要求（最少的翻转次数）。
总之，你想把它当作数学题的话，那就是超纲了。

wisdompeak2 发表于 2021-03-02 11:49:59
你可以把这道题当作解线性方程组，求解Ax=T。你需要有点线性代数的思维。
x是一个列向量，长度是m = axb，其中a，b是原矩形的维度。x的每一个元素表示棋盘的一个格子的动作（1表示翻转，0表示不

L-2 norm不代表就是总和最小吧，应该是L-1 norm才代表吧。感觉这个很难严格证明这个解一定就是最优。

很有意思的一个puzzle.
Lights out puzzle曾经是个电子游戏。这有个试玩版的：https://www.geogebra.org/m/JexnDJpt#material/KArehWn8

假设是个m乘n矩阵，如果其中m或者n的一个是比较小的数字，比如m<=10, 可以有状态压缩DP的解法。
对一般情况，楼上也有提到用矩阵求解，这里有个详细的说明 https://mathworld.wolfram.com/LightsOutPuzzle.html
这个算法可以求出是否能有一个解满足要求，但很多情况下不止有一个解。

然后应该需要在solution space里找support最小的解，即L0-optimization。因为这个题里只能选0和1，其实按L0, L1, L2,...去优化貌似都是等效的。
显然solution space不是convex的，怎么去整数优化就涉及到我的知识盲区了。
等优化大佬出场。。