Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- typedef struct pair{
- int sum;
- int valid_points;
- } pair;
- int readNumber(){
- return getchar() - 48;
- }
- int readSize(){
- int num;
- scanf("%d", &num);
- return num;
- }
- void throwOutChar(){
- getchar();
- }
- pair** createMatrix(int n, int m){
- pair** matrix = calloc(n, sizeof(pair));
- for(int i = 0; i < n; i++){
- matrix[i] = calloc(m, sizeof(pair));
- }
- return matrix;
- }
- void printMatrix(pair** matrix, int n, int m){
- for(int i = 0; i < n; i++){
- for(int j = 0; j < m; j++){
- printf("%d ", matrix[i][j].sum);
- }
- printf("\n");
- }
- }
- int main() {
- int n = readSize();
- throwOutChar();
- int m = readSize();
- throwOutChar();
- //printf("%d %d\n", n, m);
- //TODO change malloc na calloc!!!
- pair** matrix = createMatrix(n, m);
- for(int i = 0; i < n; i++){
- for(int j = 0; j< m; j++){
- int num = readNumber();
- matrix[i][j].sum = num == 2 ? -2 : num;
- if(i != 0) matrix[i][j].sum += matrix[i-1][j].sum;
- if(j != 0) matrix[i][j].sum += matrix[i][j-1].sum;
- if(i != 0 && j != 0) matrix[i][j].sum -= matrix[i-1][j-1].sum;
- if(num == 1) matrix[i][j].valid_points = 1;
- if(i != 0) matrix[i][j].valid_points += matrix[i-1][j].valid_points;
- if(j != 0) matrix[i][j].valid_points+= matrix[i][j-1].valid_points;
- if(i != 0 && j != 0) matrix[i][j].valid_points -= matrix[i-1][j-1].valid_points;
- throwOutChar();
- }
- }
- // printMatrix(matrix, n, m);
- int maximum_valid_points = 1;
- for(int i = 0; i < n; i++){
- for(int j = 0; j < m; j++){
- int min = i < j ? i : j;
- for(int k = 0; k < min; k++){
- if(k == 0) {
- //-------------------------2x2-square--------------------------------
- int check_sum = matrix[i][j].sum;
- if ((i - 1) > 0) check_sum -= matrix[i - 2][j].sum;
- if ((j - 1) > 0) check_sum -= matrix[i][j - 2].sum;
- if ((i - 1) > 0 && (j - 1) > 0) check_sum += matrix[i - 2][j - 2].sum;
- if (check_sum >= 0) {
- int result = matrix[i][j].valid_points;
- if ((i - 1) > 0) result -= matrix[i - 2][j].valid_points;
- if ((j - 1) > 0) result -= matrix[i][j - 2].valid_points;
- if ((i - 1) > 0 && (j - 1) > 0) result += matrix[i - 2][j - 2].valid_points;
- maximum_valid_points = result > maximum_valid_points ? result : maximum_valid_points;
- }
- //-------------------------2x2-square--------------------------------
- } else {
- //-------------------------3x3-square--------------------------------
- int tmp = k + 1;
- int check_sum = matrix[i][j].sum;
- check_sum -= matrix[i-1][j-1].sum;
- check_sum -= matrix[i-tmp][j-tmp].sum;
- check_sum += matrix[i-tmp][j-1].sum;
- check_sum += matrix[i-1][j-tmp].sum;
- if((i-tmp > 0)) check_sum -= matrix[i-tmp-1][j].sum;
- if((j-tmp > 0)) check_sum -= matrix[i][j-tmp-1].sum;
- if((j-tmp>0 && i-tmp>0)) check_sum += matrix[i-tmp-1][j-tmp-1].sum;
- if(check_sum >= 0){
- int result = matrix[i][j].valid_points;
- result-= matrix[i-1][j-1].valid_points;
- result-= matrix[i-tmp][j-tmp].valid_points;
- result+= matrix[i-tmp][j-1].valid_points;
- result+= matrix[i-1][j-tmp].valid_points;
- if((i-tmp > 0)) result -= matrix[i-tmp-1][j].valid_points;
- if((j-tmp > 0)) result -= matrix[i][j-tmp-1].valid_points;
- if((j-tmp>0 && i-tmp>0)) result+= matrix[i-tmp-1][j-tmp-1].valid_points;
- maximum_valid_points = result > maximum_valid_points ? result : maximum_valid_points;
- }
- }
- }
- }
- }
- printf("%d\n", maximum_valid_points);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement