题目描述

blablabla

样例

//算法思想：利用二进制暴力枚举所有的情况，输出步数最小的那一个。
//二进制枚举总共16位，一共有2的16次方种情况，时65535，不超过一个亿，所以直接暴力枚举。
//自己遇到的问题:1.写turn函数时千万不能用两个if  
               //2.op右移的时候对应位置产生疑问。 
               //3.最后输出路径时用数组来保存。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=5;
char g[N][N],backup[N][N];
int resnum[16][2];
int resnum1[16][2];
//这里的resnum用来保存当前走过的路径，resnum1用来保存当步数最小时的路径，作为最后的输出。

void turn(int x,int y){//turn函数用来改变某一行某一列的所有的字符‘+’变成减，减变成加。

    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(i==x||j==y){
                if(g[i][j]=='-') g[i][j]='+';
                else {g[i][j]='-';}
                //这里千万不要用两个if，用两个if不做任何改变
            }
        }
    }

}

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

    for(int op=0;op<=65535;op++){

        memcpy(backup, g, sizeof g);
        //每次op都是一个崭新的开始，所以要保存，后面的memcpy
        //用来恢复
        int step=0;
        int count1=0;
        for(int i=0;i<=15;i++){
        if(op>>i&1){
            //这里如果有疑问，为什么右移一位与上1是true就turn（x，y），为什么turn（x，y）呢？turn（x，y）的位置是右移
            //一位对应的位置吗？其实对应于哪个位置都是无所谓的，我们只需要保证对不同的01序列进行不同的操作就可以了。
            //所以没必要在意位置是否对应，从前往后turn就可以了。
            int x,y;
            x=i/4;
            y=i%4;
            step++;
            turn(x,y);
            resnum[count1][0]=x;//保存当前路径的数组。
            resnum[count1][1]=y;
            count1++;
         }
        bool judge=false;//判断当前op代表的01序列是否可以让全部的开关都打开。
          for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                if(g[i][j]=='+'){
                  judge=true;
                  break;
                }
            }
          }
          if(!judge){//如果当前的状态是是所有的开关都打开，就用resnum1保存当前的最短路径。
              res=min(step,res);
              for(int i=0;i<16;i++){
                  for(int j=0; j<2;j++){
                      resnum1[i][j]=resnum[i][j];
                  }
              }
          }   

        }

        memcpy(g, backup, sizeof g);//每次for一个op后都要恢复现场。
    }
    printf("%d\n",res);
        for(int i=0;i<res;i++){
            for(int j=0;j<2;j++){
            printf("%d ",resnum1[i][j]+1);
        }
        printf("\n");
    }
    return 0;
}

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla