daily pastebin goal
64%
SHARE
TWEET

Untitled

a guest Oct 12th, 2017 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef struct pair{
  5.     int sum;
  6.     int valid_points;
  7. } pair;
  8.  
  9. int readNumber(){
  10.     return getchar() - 48;
  11. }
  12.  
  13. int readSize(){
  14.     int num;
  15.     scanf("%d", &num);
  16.     return num;
  17. }
  18.  
  19. void throwOutChar(){
  20.     getchar();
  21. }
  22.  
  23. pair** createMatrix(int n, int m){
  24.     pair** matrix = calloc(n, sizeof(pair));
  25.     for(int i = 0; i < n; i++){
  26.         matrix[i] = calloc(m, sizeof(pair));
  27.     }
  28.     return matrix;
  29. }
  30.  
  31. void printMatrix(pair** matrix, int n, int m){
  32.     for(int i = 0; i < n; i++){
  33.         for(int j = 0; j < m; j++){
  34.             printf("%d ", matrix[i][j].sum);
  35.         }
  36.         printf("\n");
  37.     }
  38. }
  39.  
  40.  
  41. int main() {
  42.  
  43.     int n = readSize();
  44.     throwOutChar();
  45.     int m = readSize();
  46.     throwOutChar();
  47.  
  48.     //printf("%d %d\n", n, m);
  49.  
  50.     //TODO change malloc na calloc!!!
  51.  
  52.     pair** matrix = createMatrix(n, m);
  53.  
  54.     for(int i = 0; i < n; i++){
  55.         for(int j = 0; j< m; j++){
  56.  
  57.             int num = readNumber();
  58.             matrix[i][j].sum = num == 2 ? -2 : num;
  59.  
  60.             if(i != 0) matrix[i][j].sum += matrix[i-1][j].sum;
  61.             if(j != 0) matrix[i][j].sum += matrix[i][j-1].sum;
  62.             if(i != 0 && j != 0) matrix[i][j].sum -= matrix[i-1][j-1].sum;
  63.  
  64.             if(num == 1) matrix[i][j].valid_points = 1;
  65.             if(i != 0) matrix[i][j].valid_points += matrix[i-1][j].valid_points;
  66.             if(j != 0) matrix[i][j].valid_points+= matrix[i][j-1].valid_points;
  67.             if(i != 0 && j != 0) matrix[i][j].valid_points -= matrix[i-1][j-1].valid_points;
  68.  
  69.             throwOutChar();
  70.         }
  71.     }
  72. //    printMatrix(matrix, n, m);
  73.  
  74.     int maximum_valid_points = 1;
  75.     for(int i = 0; i < n; i++){
  76.         for(int j = 0; j < m; j++){
  77.  
  78.             int min = i < j ? i : j;
  79.             for(int k = 0; k < min; k++){
  80.  
  81.                 if(k == 0) {
  82.                     //-------------------------2x2-square--------------------------------
  83.                     int check_sum = matrix[i][j].sum;
  84.                     if ((i - 1) > 0) check_sum -= matrix[i - 2][j].sum;
  85.                     if ((j - 1) > 0) check_sum -= matrix[i][j - 2].sum;
  86.                     if ((i - 1) > 0 && (j - 1) > 0) check_sum += matrix[i - 2][j - 2].sum;
  87.  
  88.                     if (check_sum >= 0) {
  89.                         int result = matrix[i][j].valid_points;
  90.                         if ((i - 1) > 0) result -= matrix[i - 2][j].valid_points;
  91.                         if ((j - 1) > 0) result -= matrix[i][j - 2].valid_points;
  92.                         if ((i - 1) > 0 && (j - 1) > 0) result += matrix[i - 2][j - 2].valid_points;
  93.                         maximum_valid_points = result > maximum_valid_points ? result : maximum_valid_points;
  94.                     }
  95.                     //-------------------------2x2-square--------------------------------
  96.                 } else {
  97.                     //-------------------------3x3-square--------------------------------
  98.                     int tmp = k + 1;
  99.                     int check_sum = matrix[i][j].sum;
  100.                     check_sum -= matrix[i-1][j-1].sum;
  101.                     check_sum -= matrix[i-tmp][j-tmp].sum;
  102.                     check_sum += matrix[i-tmp][j-1].sum;
  103.                     check_sum += matrix[i-1][j-tmp].sum;
  104.  
  105.                     if((i-tmp > 0)) check_sum -= matrix[i-tmp-1][j].sum;
  106.                     if((j-tmp > 0)) check_sum -= matrix[i][j-tmp-1].sum;
  107.                     if((j-tmp>0 && i-tmp>0)) check_sum += matrix[i-tmp-1][j-tmp-1].sum;
  108.  
  109.                     if(check_sum >= 0){
  110.                         int result = matrix[i][j].valid_points;
  111.                         result-= matrix[i-1][j-1].valid_points;
  112.                         result-= matrix[i-tmp][j-tmp].valid_points;
  113.                         result+= matrix[i-tmp][j-1].valid_points;
  114.                         result+= matrix[i-1][j-tmp].valid_points;
  115.                         if((i-tmp > 0)) result -= matrix[i-tmp-1][j].valid_points;
  116.                         if((j-tmp > 0)) result -= matrix[i][j-tmp-1].valid_points;
  117.                         if((j-tmp>0 && i-tmp>0)) result+= matrix[i-tmp-1][j-tmp-1].valid_points;
  118.                         maximum_valid_points = result > maximum_valid_points ? result : maximum_valid_points;
  119.                     }
  120.                 }
  121.  
  122.             }
  123.         }
  124.     }
  125.  
  126.  
  127.     printf("%d\n", maximum_valid_points);
  128.     return 0;
  129. }
RAW Paste Data
Top