算法 DFS 暴力枚举

(暴力枚举) $O(n^2)$

把小爷折磨的 ~, 当我看到这道题的时候就直接想到暴力枚举一共16 * 2^16, 1S完全可以过掉但是当我写的时候
感觉思路没错就是答案错误,后来才知道,递归条件位置放错了，我应该先放可以更新答案的,再放递归出口,这次涨知识啦

时间复杂度

参考文献

C++ 代码

#include <iostream> // 0 2 3 12 14 15
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

const int N = 16, INF = 1e9;
char g[N][N];
int ans = INF;
vector<int> nums;
int a[N] = {0, 2, 3, 12, 14, 15};
vector<int> num;

void init()
{
    for(int i = 0; i < 6; i ++)
        num.push_back(a[i]);
}
void turn(int x, int y)
{
    for(int i = 0; i < 4; i ++)
    {
        if(g[x][i] == '+')g[x][i] = '-';
        else g[x][i] = '+';
        if(g[i][y] == '+')g[i][y] = '-';
        else g[i][y] = '+';
    }
    if(g[x][y] == '+')g[x][y] = '-';
    else g[x][y] = '+';
}

bool check()
{
    for(int i = 0; i < 4; i ++)
        for(int j = 0; j < 4; j ++)
            if(g[i][j] == '+')return false;
    return true;
}

void print()
{
    for(int i = 0; i < 4; i ++)puts(g[i]);
    puts("");
}

void dfs(int u, int step)
{
    if(step >= ans)return ;
    if(check())
    {
        for(auto x : nums)
        num.push_back(x);
        ans = step;
    }
    if(u == 16)
    {

        return ;
    }

    dfs(u + 1, step);
    int x = u / 4, y = u % 4;
    char m[N][N];
    memcpy(m, g, sizeof g);
    turn(x, y);
    nums.push_back(u);
    dfs(u + 1, step + 1);
    nums.pop_back();
    memcpy(g, m, sizeof m);
    if(check())ans = step;
}

void change()
{
    for(auto u : num)
    {
        int x = u / 4, y = u % 4;
        turn(x, y);
        print();
    }
    if(check())cout << "YES" << endl;
}

int main()
{
    for(int i = 0; i < 4; i ++)cin >> g[i];
    dfs(0, 0);

    cout << ans << endl;
    for(auto u : num)
    {
        int x = u / 4, y = u % 4;
        cout << x + 1 << ' ' << y + 1 << endl;
    }
    return 0;
}