SHARE
TWEET

Untitled

a guest Feb 21st, 2019 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <string>
  6. #include <cctype>
  7. #include <stack>
  8. #include <queue>
  9. #include <list>
  10. #include <vector>
  11. #include <map>
  12. #include <sstream>
  13. #include <cmath>
  14. #include <bitset>
  15. #include <utility>
  16. #include <set>
  17. #include <numeric>
  18. #include <ctime>
  19.  
  20. using namespace std;
  21. typedef pair<int, int> ii;
  22. typedef vector<int> vi;
  23. typedef vector<vi> vii;
  24. typedef long long int ll;
  25.  
  26. #define INF 1000000000
  27. #define MAX 16
  28.  
  29. int grid[MAX][MAX];
  30. int exec;
  31. int n;
  32. priority_queue<int, vi, greater<int> > leo;
  33.  
  34.  
  35. bool oddpar(int i, int j){
  36.     int par = 0;
  37.     if (i > 0){
  38.         if (grid[i-1][j]) par++;
  39.     }
  40.     if (i < n-1){
  41.         if (grid[i+1][j]) par++;
  42.     }
  43.     if (j > 0){
  44.         if (grid[i][j-1]) par++;
  45.     }
  46.     if (j < n-1){
  47.         if (grid[i][j+1]) par++;
  48.     }
  49.    
  50.     return (par%2);
  51. }
  52.  
  53. int turn (int i, int j){
  54.     int odds=0;
  55.     if (grid[i][j]) grid[i][j] = 0;
  56.     else grid[i][j] = 1;
  57.    
  58.     if (i > 0) if (oddpar(i-1, j)) odds++; else odds--;
  59.     if (i < n-1) if (oddpar(i+1, j)) odds++; else odds--;
  60.     if (j > 0) if (oddpar(i, j-1)) odds++; else odds--;
  61.     if (j < n-1) if(oddpar(i, j+1)) odds++; else odds--;
  62.    
  63.     return odds;
  64. }
  65.  
  66. void backtrack(int i, int j, int odds, int moves){
  67.         if (odds == 0) {
  68.            for (int i = 0; i<n; i++) {for (int j = 0; j<n; j++) printf("%d ", grid[i][j]); cout<<endl; }
  69.             leo.push(moves);
  70.             return;
  71.         }
  72.         if (j == n) {backtrack(i+1, 0, odds, moves); return;}
  73.         if (i == n) { return;}
  74.        
  75.         if (i == 0){
  76.             backtrack(i, j+1, odds, moves); // nao mexe..
  77.             if (grid[i][j] == 0){ // se for 0, troca e vai..
  78.             int a = turn(i, j);
  79.             backtrack(i, j+1, odds+a, moves+1);
  80.             turn(i, j); // volta.
  81.             }
  82.         } else {
  83.        
  84.             if (oddpar(i-1, j)){
  85.                 if (grid[i][j] == 0){
  86.                 int a = turn(i,j);
  87.                 backtrack(i, j+1, odds+a, moves+1);
  88.                     turn(i,j);
  89.                 } else {
  90.                     return; // não dá pra fazer nada :(
  91.                 }
  92.             } else {
  93.                 backtrack(i, j+1, odds, moves);
  94.             }
  95.            
  96.            
  97.         }
  98.     }
  99.  
  100. int main(){
  101.    
  102.     int t; scanf("%d", &t);
  103.     exec=0;
  104.     while (t--){
  105.         exec++;
  106.         while (!leo.empty()) leo.pop();
  107.         scanf("%d", &n);
  108.         for (int i = 0; i<n; i++){
  109.             for (int j = 0; j<n; j++) scanf("%d", &grid[i][j]);
  110.         }
  111.        
  112.         int odds = 0;
  113.         for (int i = 0; i<n; i++) for (int j = 0; j<n; j++) odds += oddpar(i,j);
  114.        
  115.         printf("Case %d: ", exec);
  116.         if (odds > 0) {backtrack(0, 0, odds, 0);
  117.             if (leo.empty()) { cout << "-1" << endl; } else cout << leo.top() << endl;
  118.         } else cout << "0" << endl;
  119.        
  120.     }
  121.     return 0;
  122. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top