题目描述

飞行员兄弟

暴力递归
将’-‘和’+’,用0和1表示，这样转换状态会更方便，用!取反就好

样例

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
int handle[4][4]; //0表示关，1表示开
int mi=20;
int line1[20][2];
int line2[20][2];

bool isright(){
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(!handle[i][j]){
                return false;
            }
        }
    }
    return true;
}

void turn(int x,int y){
    for(int i=0;i<4;i++){
        handle[x][i]=!handle[x][i];
    }
    for(int i=0;i<4;i++){
        handle[i][y]=!handle[i][y];
    }
    handle[x][y]=!handle[x][y];
    return ;
}

void dfs(int k,int h){
    for(int i=k;i<16;i++){
        turn(i/4,i-(i/4)*4);
        line2[h][0]=i/4;
        line2[h][1]=i-(i/4)*4;

        dfs(i+1,h+1);

        turn(i/4,i-(i/4)*4);
    }
    if(isright()&&h<mi){
        memcpy(line1,line2,sizeof(line2));
        mi=h;
    }
    return ;
}

int main(){
    char c;
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            c=getchar();
            if(c=='+'){
                handle[i][j]=0;
            }
            else if(c=='-'){
                handle[i][j]=1;
            }
        }
        getchar();
    }

    dfs(0,0);

    printf("%d\n",mi);
    for(int i=0;i<mi;i++){
        printf("%d %d\n",line1[i][0]+1,line1[i][1]+1);
    }
    return 0;
}

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla