fork(1) download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cstring>
  4. #include <bitset>
  5. using namespace std;
  6.  
  7. long long mat[1 << 16];
  8. long long arr[] = {-1,-4,0,1,4};
  9.  
  10. long long soloUno(long long x,long long i) {
  11.   x ^= (1 << i);
  12.   return x;
  13. }
  14.  
  15. bool potenciaDeDos(long long n) {
  16.   if(n == 0 or n == 1) return true;
  17.   if(n % 2 != 0) return false;
  18.   return potenciaDeDos(n >> 1);
  19. }
  20.  
  21. long long todos(long long x,long long i) {
  22.   x ^= (1 << i);
  23.   long long aux = i - 1;
  24.   if(aux >= 0) x ^= (1 << aux);
  25.   aux = i - 4;
  26.   if(aux >= 0) x ^= (1 << aux);
  27.   aux = i + 1;
  28.   if(aux < 16) x ^= (1 << aux);
  29.   aux = i + 4;
  30.   if(aux < 16) x ^= (1 << aux);
  31.   return x;
  32. }
  33.  
  34. long long dp(long long n) {
  35.   long long &r = mat[n];
  36.   if(r == -1 and potenciaDeDos(n)) r = 2;
  37.   if(r == -1) {
  38.     r = 100000;
  39.     for(long long i = 0; i < 16; ++i) {
  40.       r = min(r,min(2 + dp(soloUno(n,i)),1 + dp(todos(n,i))));
  41.     }
  42.   }
  43.   return r;
  44. }
  45.  
  46. int main() {
  47.   long long lim = 1 << 16;
  48.   memset(mat,-1,sizeof mat);
  49.   mat[0] = 0;
  50.   for(long long i = 1; i < lim; ++i) mat[i] = dp(i);
  51.   long long T;
  52.   cin >> T;
  53.   string s,total;
  54.   while(T--) {
  55.     total = "";
  56.     for(long long i = 0; i < 4; ++i) {
  57.       cin >> s;
  58.       total += s;
  59.     }
  60.     bitset<20> bs(total);
  61.     cout << mat[bs.to_ulong()] << endl;
  62.   }
  63.   return 0;
  64. }
  65.  
Success #stdin #stdout 0.08s 8352KB
comments (?)
stdin
copy 
5
1100
1000
0000
0000
0100
1110
0100
0000
1000
0000
0000
0000
1100
1000
0000
0001
1011
1010
0000
0000
stdout
copy 
1
1
2
3
7
https://ideone.com/Z7qoof
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!