#include #include #define MAXKL 1000 #define MAXMN 1000 #define MAXF (MAXKL*MAXKL) int R, C, M, N; char mapa[MAXKL+2][MAXKL+2]; int mistnost[MAXKL+2][MAXKL+2]; int zasobnik[MAXF][2]; int velikost_zasobniku; int prekryv[MAXF+1]; int pocet_mistnosti; int akt_mistnosti, max_mistnosti; void nacti_vstup(void) { scanf("%d%d%d%d", &R, &C, &M, &N); for (int i = 1; i <= R; i++) scanf("%s", mapa[i] + 1); } void prohod(char *x, char *y) { char t; t=*x; *x=*y; *y=t; } void transponuj(void) { int i, j, t; int RC = R < C ? R : C; for (i = 0; i <= R + 1; i++) for (j = 0; j <= C + 1; j++) if (i > RC + 1 || j > RC + 1 || i < j) prohod(&mapa[i][j], &mapa[j][i]); t=R; R=C; C=t; t=M; M=N; N=t; } void zkus_jit(int x, int y) { if (!mistnost[x][y] && mapa[x][y] == '.') { mistnost[x][y] = pocet_mistnosti; zasobnik[velikost_zasobniku][0] = x; zasobnik[velikost_zasobniku][1] = y; velikost_zasobniku++; } } void najdi_mistnosti(void) { for (int i = 1; i <= R; i++) for (int j = 1; j <= C; j++) if (!mistnost[i][j] && mapa[i][j] == '.') { pocet_mistnosti++; zkus_jit(i, j); while (velikost_zasobniku > 0) { velikost_zasobniku--; int x = zasobnik[velikost_zasobniku][0]; int y = zasobnik[velikost_zasobniku][1]; zkus_jit(x - 1, y); zkus_jit(x + 1, y); zkus_jit(x, y - 1); zkus_jit(x, y + 1); } } } void zvetsi_prekryv(int i, int j) { if (mistnost[i][j] && ++prekryv[mistnost[i][j]] == 1) akt_mistnosti++; } void zmensi_prekryv(int i, int j) { if (mistnost[i][j] && --prekryv[mistnost[i][j]] == 0) akt_mistnosti--; } void vyzkousej_radek(int r) { int j, k; for (j = 1; j <= N; j++) for (k = -1; k <= M; k++) zvetsi_prekryv(r + k, j); for (k = 0; k < M; k++) zvetsi_prekryv(r + k, N + 1); if (akt_mistnosti > max_mistnosti) max_mistnosti = akt_mistnosti; for (j = 1; j <= C - N; j++) { for (k = 0; k < M; k++) { zmensi_prekryv(r + k, j - 1); zvetsi_prekryv(r + k, j + N + 1); } zmensi_prekryv(r - 1, j); zmensi_prekryv(r + M, j); zvetsi_prekryv(r - 1, j + N); zvetsi_prekryv(r + M, j + N); if (akt_mistnosti > max_mistnosti) max_mistnosti = akt_mistnosti; } for (j = C - N + 1; j <= C; j++) for (k = -1; k <= M; k++) zmensi_prekryv(r + k, j); for (k = 0; k < M; k++) zmensi_prekryv(r + k, C - N); } void vyzkousej_diry(void) { for (int i = 1; i <= R - M + 1; i++) vyzkousej_radek(i); } int main(void) { nacti_vstup(); if (M > N) transponuj(); najdi_mistnosti(); vyzkousej_diry(); printf("%d\n", max_mistnosti); return 0; }