Go to diff to previous submission
#include <cstdio> #include <cstring> char map[1024][1024]; int Ar, Ac, Tr, Tc; int width, height; static inline int get_Cmin(){ for (int c = 0; c < Ac; ++c){ for (int r = 0; r < Ar; ++r){ if (map[r][c] == 'X'){ return c; } } } return Ar; } static inline int get_Cmax(){ for (int c = Ac - 1; c >= 0; c--){ for (int r = Ar -1; r >= 0; r--){ if (map[r][c] == 'X'){ return c; } } } return 0; } static inline int get_Rmax(){ for (int r = Ar - 1; r >= 0; r--){ for (int c = Ac - 1; c >= 0; c--){ if (map[r][c] == 'X'){ return r; } } } return 0; } static inline int get_Rmin(){ for (int r = 0; r < Ar; r++){ for (int c = 0; c < Ac; c++){ if (map[r][c] == 'X'){ return r; } } } return Ac; } bool checkRectangle(int c, int r, int Cmin, int Rmin) { //radek int radek = (Rmin+r*Tr >= 0)? Rmin+r*Tr : 0; int sloupec = (Cmin+(c+1)*Tc-1 >= 0)? Cmin+(c+1)*Tc-1 : 0; int sloupecPP = (Cmin+c*Tc >= 0)? Cmin+c*Tc : 0; for (int i = sloupecPP; i < Cmin + (c+1)*Tc; i++) { if (map[Rmin+(r+1)*Tr-1][i] == 'X' || map[radek][i] == 'X'){ return true; } } //sloupec for (int i = radek; i < Rmin+(r+1)*Tr; i++){ if (map[i][Cmin+(c+1)*Tc-1] == 'X' || map[i][sloupec] == 'X'){ return true; } } return false; } int placement_min(int Cmin, int Rmin){ int res = width * height; for (int c = 0; c < width; c++){ for (int r = 0; r < height; r++){ if (!checkRectangle(c, r, Cmin, Rmin)){ // printf("Throwing out: %d %d\n", c, r); res--; } } } return res; } int main(){ while (scanf("%d %d %d %d", &Ar, &Ac, &Tr, &Tc) != EOF){ for (int r = 0; r < Ar; r++){ memset(map[r], 0, Ac); } for (int r = 0; r < Ar; ++r){ scanf("%s%*c", map[r]); } int Cmin = get_Cmin(); int Cmax = get_Cmax(); int Rmin = get_Rmin(); int Rmax = get_Rmax(); // printf("Cmin: %d Cmax: %d Rmin: %d Rmax: %d\n", Cmin, Cmax, Rmin, Rmax); width = (Cmax - Cmin + Tc) / Tc; height = (Rmax - Rmin + Tr) / Tr; int res = width * height; int diff_width = width*Tc - Cmax; int diff_height = height*Tr - Rmax; int Cmin_new = Cmin; for (int i = 0; i < diff_width; i++){ // for (int j = 0; j < diff_height; j++){ int tmp = placement_min(Cmin -i, Rmin); // printf("tmp: %d\n", tmp); if (tmp < res){ Cmin_new = Cmin - i; res = tmp; } // } } for (int i = 0; i < diff_height; i++){ int tmp = placement_min(Cmin_new, Rmin - i); if (tmp < res){ res = tmp; } } printf("%d\n", res); } }
--- c5.s1139.cteam024.fm.cpp.0.fm.cpp +++ c5.s1155.cteam024.fm.cpp.0.fm.cpp @@ -112,14 +112,15 @@ for (int i = 0; i < diff_width; i++){ - for (int j = 0; j < diff_height; j++){ - int tmp = placement_min(Cmin -i, Rmin - j); +// for (int j = 0; j < diff_height; j++){ + int tmp = placement_min(Cmin -i, Rmin); // printf("tmp: %d\n", tmp); if (tmp < res){ + Cmin_new = Cmin - i; res = tmp; } - } + // } } -/* for (int i = 0; i < diff_height; i++){ + for (int i = 0; i < diff_height; i++){ int tmp = placement_min(Cmin_new, Rmin - i); if (tmp < res){ @@ -127,5 +128,5 @@ } } -*/ + printf("%d\n", res); }