Advertisement
Guest User

Untitled

a guest
Oct 12th, 2017
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.36 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement