SHARE
TWEET

Untitled

a guest Aug 18th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <string.h>
  3. using namespace std;
  4.  
  5. const int MAX = 25;
  6.  
  7. int t, d, w, k, result, num[MAX], map[MAX][MAX], data[MAX][MAX];
  8. bool flag, check[MAX];
  9.  
  10. bool checkK() {
  11.     int cnt = 1, sum = 0;
  12.    
  13.   for(int i=1;i<=w;i++) {
  14.     int inx = data[1][i];
  15.     cnt = 1;
  16.        
  17.     for(int j=2;j<=d;j++) {
  18.       if(data[j][i] == inx) cnt++;
  19.       else {
  20.         if(j == d - k + 2) break;
  21.        
  22.         inx = data[j][i];
  23.         cnt = 1;
  24.       }
  25.            
  26.       if(cnt >= k) {
  27.         sum++;
  28.         break;
  29.       }
  30.     }
  31.        
  32.     if(sum != i) return false;
  33.   }
  34.            
  35.   return true;
  36. }
  37.            
  38. void getNum(int x, int n) {
  39.     if(flag) return;
  40.    
  41.   if(x == n) {
  42.     if(checkK()) {
  43.       result = n;
  44.       flag = true;
  45.     }
  46.   }
  47.   else {
  48.     int arr[MAX] = {0,}, a_inx = 0;
  49.    
  50.     for(int i=1;i<=d;i++) {
  51.       if(!check[i]) {
  52.         num[x] = i;
  53.         check[i] = true;
  54.         arr[a_inx++] = i;
  55.  
  56.         for(int j=1;j<=w;j++) {
  57.           data[num[x]][j] = 0;
  58.         }
  59.  
  60.         getNum(x+1, n);
  61.  
  62.         for(int j=1;j<=w;j++) {
  63.           data[num[x]][j] = 1;
  64.         }
  65.  
  66.         getNum(x+1, n);
  67.  
  68.         for(int j=1;j<=w;j++) {
  69.           data[num[x]][j] = map[num[x]][j];
  70.         }
  71.  
  72.         num[x] = 0;
  73.       }
  74.     }
  75.    
  76.     for(int i=0;i<a_inx;i++) check[arr[i]] = false;
  77.   }
  78. }
  79.  
  80. int main() {
  81.     scanf("%d", &t);
  82.    
  83.   for(int v=1;v<=t;v++) {
  84.     scanf("%d %d %d", &d, &w, &k);
  85.        
  86.     for(int i=1;i<=d;i++) {
  87.       for(int j=1;j<=w;j++) {
  88.         scanf("%d", &map[i][j]);
  89.         data[i][j] = map[i][j];
  90.       }
  91.     }
  92.        
  93.     if(k != 1) {
  94.       if(!checkK()){
  95.         int cnt =1;
  96.         while(!flag) {
  97.           getNum(0, cnt);
  98.           cnt++;
  99.         }
  100.         for(int i=1;i<=d;i++) check[i] = false;
  101.       }
  102.     }
  103.        
  104.     printf("#%d %d\n", v, result);
  105.  
  106.     result = 0, flag = false;
  107.  
  108.     for(int i=1;i<=d;i++) {
  109.       for(int j=1;j<=w;j++) {
  110.         map[i][j] = 0;
  111.         data[i][j] = 0;
  112.       }
  113.     }
  114.   }
  115.    
  116.   return 0;
  117. }
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