mickypinata

GCJ2018-1A1: Waffle Choppers

Jun 21st, 2021
566
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 100;
  5.  
  6. int qsum[N + 10][N + 10];
  7. int row, col, rCut, cCut;
  8.  
  9. int getsum(int x1, int y1, int x2, int y2){
  10.     return qsum[x2][y2] - qsum[x1 - 1][y2] - qsum[x2][y1 - 1] + qsum[x1 - 1][y1 - 1];
  11. }
  12.  
  13. vector<int> divided;
  14. bool divideC(int c, int cut, int sum){
  15.     if(cut == 0){
  16.         return true;
  17.     }
  18.     for(int i = c; i <= col - cut; ++i){
  19.         if(c == 1){
  20.             bool broken = false;
  21.             for(int j = 0; j < (int)divided.size() - 1; ++j){
  22.                 if(j == 0){
  23.                     sum = getsum(divided[j] + 1, c, divided[j + 1], i);
  24.                 } else if(getsum(divided[j] + 1, c, divided[j + 1], i) != sum){
  25.                     broken = true;
  26.                     break;
  27.                 }
  28.             }
  29.             if(!broken && getsum(1, i + 1, row, col) == sum * cut * (rCut + 1) && divideC(i + 1, cut - 1, sum)){
  30.                 return true;
  31.             }
  32.         } else {
  33.             bool broken = false;
  34.             for(int j = 0; j < (int)divided.size() - 1; ++j){
  35.                 if(getsum(divided[j] + 1, c, divided[j + 1], i) != sum){
  36.                     broken = true;
  37.                     break;
  38.                 }
  39.             }
  40.             if(!broken && getsum(1, i + 1, row, col) == sum * cut * (rCut + 1) && divideC(i + 1, cut - 1, sum)){
  41.                 return true;
  42.             }
  43.         }
  44.     }
  45.     return false;
  46. }
  47.  
  48. bool divideR(int r, int cut, int sum){
  49.     if(cut == 0){
  50.         divided.push_back(row);
  51.         return divideC(1, cCut, -1);
  52.         divided.pop_back();
  53.     }
  54.     for(int i = r; i <= row - cut; ++i){
  55.         if(r == 1){
  56.             divided.push_back(i);
  57.             sum = getsum(r, 1, i, col);
  58.             if(getsum(i + 1, 1, row, col) == sum * cut && divideR(i + 1, cut - 1, sum)){
  59.                 return true;
  60.             }
  61.             divided.pop_back();
  62.         } else if(getsum(r, 1, i, col) == sum){
  63.             divided.push_back(i);
  64.             if(getsum(i + 1, 1, row, col) == sum * cut && divideR(i + 1, cut - 1, sum)){
  65.                 return true;
  66.             }
  67.             divided.pop_back();
  68.         }
  69.     }
  70.     return false;
  71. }
  72.  
  73. int main(){
  74.  
  75.     int Q;
  76.     scanf("%d", &Q);
  77.     for(int q = 1; q <= Q; ++q){
  78.         cout << "Case #" << q << ": ";
  79.         divided.assign(1, 0);
  80.         scanf("%d%d%d%d", &row, &col, &rCut, &cCut);
  81.         for(int i = 1; i <= row; ++i){
  82.             for(int j = 1; j <= col; ++j){
  83.                 char c;
  84.                 scanf(" %c", &c);
  85.                 if(c == '@'){
  86.                     qsum[i][j] = 1;
  87.                 } else if(c == '.'){
  88.                     qsum[i][j] = 0;
  89.                 }
  90.                 qsum[i][j] += qsum[i - 1][j] + qsum[i][j - 1] - qsum[i - 1][j - 1];
  91.             }
  92.         }
  93.         if(divideR(1, rCut, -1)){
  94.             cout << "POSSIBLE\n";
  95.         } else {
  96.             cout << "IMPOSSIBLE\n";
  97.         }
  98.     }
  99.  
  100.     return 0;
  101. }
  102.  
RAW Paste Data