SHARE
TWEET

Untitled

a guest Aug 19th, 2019 63 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. struct point{
  6.   int y, x, k;
  7. };
  8.  
  9. const int MAX = 15;
  10.  
  11. int t, sum, cnt, a_inx, m = 1, paper[10], map[MAX][MAX], dx[10][MAX], dy[10][MAX];
  12. bool check[MAX][MAX], flag;
  13. point arr[120];
  14.  
  15. void checkList() {
  16.   for(int k=2;k<6;k++) {
  17.     int inx = 0;
  18.     for(int i=0;i<k;i++) {
  19.       if(i == k-1) {
  20.         for(int j=0;j<=i;j++) {
  21.           dx[k][inx++] = i;
  22.         }
  23.       }
  24.       else dx[k][inx++] = i;
  25.      
  26.     }
  27.     inx = 0;
  28.     for(int i=k-1;i>=0;i--) {
  29.       if(i == k-1) {
  30.         for(int j=i;j>=0;j--) {
  31.           dy[k][inx++] = i;
  32.         }
  33.       }
  34.       else dy[k][inx++] = i;
  35.     }
  36.   }
  37. }
  38.  
  39. void checkMap(int y, int x, int k) {
  40.   if(k == 0) return;
  41.   int n = 0;
  42.  
  43.   if(k == 1) n = 1;
  44.   else if(k == 2) n = 3;
  45.   else if(k == 3) n = 5;
  46.   else if(k == 4) n = 7;
  47.   else if(k == 5) n = 9;
  48.  
  49.   for(int i=0;i<n;i++) {
  50.     int nextX = x + dx[k][i], nextY = y + dy[k][i];
  51.     check[nextY][nextX] = true;
  52.   }
  53.   sum -= n;
  54.   checkMap(y, x, k-1);
  55. }
  56.  
  57. bool checkPaper(int y, int x, int k) {
  58.   int n = 0;
  59.  
  60.   if(k == 2) n = 3;
  61.   else if(k == 3) n = 5;
  62.   else if(k == 4) n = 7;
  63.   else if(k == 5) n = 9;
  64.  
  65.   for(int i=0;i<n;i++) {
  66.     int nextX = x + dx[k][i], nextY = y + dy[k][i];
  67.    
  68.     if(nextX < 0 || nextX > 9 || nextY < 0 || nextY > 9 || map[nextY][nextX] == 0 || check[nextY][nextX]) {
  69.       return false;
  70.     }
  71.   }
  72.  
  73.   return true;
  74. }
  75.  
  76. int main() {
  77.   checkList();
  78.   for(int i=1;i<=5;i++) paper[i] = 5;
  79.  
  80.   scanf("%d", &t);
  81.  
  82.   for(int v=1;v<=t;v++) {
  83.     for(int i=0;i<10;i++) {
  84.       for(int j=0;j<10;j++) {
  85.         scanf("%d", &map[i][j]);
  86.         if(map[i][j] == 1) {
  87.           sum++;
  88.           arr[a_inx].y = i, arr[a_inx].x = j;
  89.           a_inx++;
  90.         }
  91.       }
  92.     }
  93.  
  94.     for(int i=0;i<a_inx;i++) {
  95.       int k = 2;
  96.       while(1) {
  97.         if(k == 6) {
  98.           arr[i].k = k-1;
  99.           if(m < k-1) m = k-1;
  100.           break;
  101.         }
  102.        
  103.         if(checkPaper(arr[i].y, arr[i].x, k)) k++;
  104.         else {
  105.           arr[i].k = k-1;
  106.           if(m < k-1) m = k-1;
  107.           break;
  108.         }
  109.       }
  110.     }
  111.    
  112.     for(int i=m;i>=2;i--) {
  113.       for(int j=0;j<a_inx;j++) {
  114.         if(arr[j].k == i && !check[arr[j].y][arr[j].x]) {
  115.           if(!checkPaper(arr[j].y, arr[j].x, i)) continue;
  116.           else if(paper[i] == 0) continue;
  117.  
  118.           checkMap(arr[j].y, arr[j].x, i);
  119.           paper[i]--;
  120.           cnt++;
  121.         }
  122.       }
  123.       if(sum == 0) break;
  124.     }
  125.  
  126.     if(sum != 0) {
  127.       if(sum > paper[1]) sum = 1;
  128.       else {
  129.         cnt += sum;
  130.         sum = 0;
  131.       }
  132.     }
  133.    
  134.     if(sum != 0) cnt = -1;
  135.     printf("#%d %d\n", v, cnt);
  136.    
  137.     sum = 0, cnt = 0, flag = false, m = 1, a_inx = 0;
  138.     memset(check, 0, sizeof(check));
  139.     memset(map, 0, sizeof(map));
  140.     memset(arr, 0, sizeof(arr));
  141.     for(int i=1;i<=5;i++) paper[i] = 5;
  142.   }
  143.  
  144.   return 0;
  145. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top