题目链接

算法竞赛进阶指南-8.费解的开关

Method1 : 位运算+枚举+递推

• 对第一行所有灯按不按的所有情况的枚举
  • 以保证第一行为全1为目的，用第一行的当前状态确定第二行的按法，接下来每行依次类推
  • 当最后一行没法全1，说明不满足

#include <iostream>
#include <cstring>

using namespace std;

const int N = 5 + 7;
const int INF = 0x3f3f3f3f;
const int dir[5][2] = {{0, 0}, {0, -1}, {1, 0}, {0, 1}, {-1, 0}};

char graph[N][N];

// 开关
void turn(int x, int y) { 
    for (auto d : dir) {
        int xn = x + d[0];
        int yn = y + d[1];
        if (0 <= xn && xn < 5 && 0 <= yn && yn < 5) {
            graph[xn][yn] ^= 1; // 异或配对
        }
    }
}

int main() {
    int m; 
    cin >> m;
    while (m --) {
        for (int i = 0; i < 5; i ++) {
            scanf("%s", graph[i]);
        }
        
        //枚举
        int res = INF;
        for (int k = 0; k < 1 << 5; k ++) {
            char backup[N][N];
            memcpy(backup, graph, sizeof graph);
            
            int cnt = 0;
            for (int j = 0; j < 5; j ++) {
                if (k >> j & 1) {
                    turn(0, j);
                    cnt ++;
                }
            }
            
            // 根据第一行递推
            for (int i = 0; i < 4; i ++) {
                for (int j = 0; j < 5; j ++) {
                    if (graph[i][j] == '0') {
                        turn(i + 1, j);
                        cnt ++;
                    }   
                }
            }
            
            bool flag = true;
            for (int j = 0; j < 5; j ++) {
                if (graph[4][j] == '0') {
                    flag = false;
                    break;
                }
            }
            
            if(flag) res = min(res, cnt);
            memcpy(graph, backup, sizeof backup);
        }
        
        if (res <= 6) cout << res << endl;
        else cout << -1 << endl;
    }
    
    return 0;
}

复杂度分析

• 时间复杂度${O(m * 32 * (25 * 5 + 5))}$， 其中$m$为m次询问，32为第一行的枚举，25 为棋盘, *5为按开关的dir[5]个方向， +5为判断最后一行， 还要额外加上两次memcpy的时间复杂度（O(5 * 5)）。

• 空间复杂度${O(1)}$。

Method2 : 广度优先遍历-递归

我的最初想法 ： 把图转为25位的数来做，利用 i * n + j，确定当前位数，然后判dfs判断6步以内能否出现25个1， 但这样也要注意上下左右的变法

复杂度分析