POJ 2965 The Pilots Brothers' refrigerator-白红宇

POJ 2965 The Pilots Brothers' refrigerator

阅读量：4671 次

发布时间：2019-06-09

本文共 1339 字，大约阅读时间需要 4 分钟。

题意：有4×4个开关，每改变一个开关的状态，会同时改变同一行和同一列开关的状态，给出初始状态，求最少需要多少步能把所有开关都变成开，并输出方案。

解法：枚举+剪枝。直接暴力枚举竟然T了……觉得不太科学……2^16*16的复杂度而已……只好加了一个剪枝，记录当前已经枚举过的最佳答案，后来就只枚举到最佳答案，如果超过了最佳答案的步数说明肯定不是最佳方案。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define LL long longusing namespace std;int main(){ ios :: sync_with_stdio(false); char maze[4][5]; while(cin >> maze[0]) { for(int i = 1; i < 4; i++) cin >> maze[i]; int maxn = 1 << 16; int ans = 1000000, pos = 0; for(int i = 0; i < maxn; i++) { int res = 0; int cnt[4][4] = {0}; int flag = 1; for(int j = 0; j < 16; j++) { if(i & (1 << j)) { res++; if(res > ans)//剪枝 { flag = 0; break; } for(int k = 0; k < 4; k++) { cnt[j / 4][k]++; cnt[k][j % 4]++; } cnt[j / 4][j % 4]--; } } for(int j = 0; j < 4 && flag; j++) for(int k = 0; k < 4 && flag; k++) { int tmp = maze[j][k] == '+' ? 1 : 0; tmp += cnt[j][k]; if(tmp & 1) flag = 0; } if(flag && (res < ans)) { ans = res; pos = i; } } if(ans != 1000000) cout << ans << endl; else cout << "0" << endl; for(int i = 0; i < 16; i++) { if(pos & (1 << i)) { cout << i / 4 + 1 << ' ' << i % 4 + 1 << endl; } } } return 0;}

转载于:https://www.cnblogs.com/Apro/p/4859156.html

你可能感兴趣的文章

编写高质量代码改善C#程序的157个建议——建议50：在Dispose模式中应区别对待托管资源和非托管资源...