704. Bulb Switcher II

lass Solution {
public:
    /**
     * @param n: number of lights
     * @param m: number of operations
     * @return: the number of status
     */
    int flipLights(int n, int m) {
        // write your code here
        unordered_set<string> set; 
        if(n == 0 || m == 0){
            return 1; 
        }
        string s = "";
        for(int i = 0; i < n; i++){
            s += "1"; 
        }
        set.insert(s); 
        for(int i = 0; i < m; i++){
            unordered_set<string> tmp; 
            for(auto str : set){
                string s1 = str, s2 = str, s3 = str, s4 = str; 
                for(int j = 0; j < n; j++){
                    s1[j] = s1[j] == '0' ? '1' : '0'; 
                    if(2 * j < n){
                        s2[2 * j] = s2[2 * j] == '0' ? '1' : '0'; 
                    }
                    if(2 * j + 1 < n){
                        s3[2 * j + 1] = s3[2 * j + 1] == '0' ? '1' : '0'; 
                    }
                    if(3 * j + 1 < n){
                        s4[3 * j + 1] = s4[3 * j + 1] == '0' ? '1' : '0'; 
                    }
                }
                tmp.insert(s1);
                tmp.insert(s2);
                tmp.insert(s3);
                tmp.insert(s4); 
            }
            set = tmp; 
        }
        return set.size(); 
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44