Go to diff to previous submission
#include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <utility> #include <string> #include <deque> #include <list> #include <map> #include <queue> #include <set> #include <stack> #include <vector> using namespace std; //#define debug printf #define debug blackhole void blackhole(...) {} #define MAXN 2000 int Ar,Ac,Tr,Tc; bool TAKEN[MAXN][MAXN]; // [Ar][Ac] int P[MAXN][MAXN]; // !!! od -Tr, -Tc do Ar, Ac int Q[MAXN][MAXN]; inline int is_taken(int x, int y) { if (x < 0 || y < 0 || x >= Ar || y >= Ac) return 0; return TAKEN[x][y] ? 1 : 0; } void build() { for (int i=0;i<MAXN;i++) { for (int j=0;j<MAXN;j++) { P[i][j] = 0; Q[i][j] = 0; } } for (int r = -Tr; r < Ar + Tr; r++){ for (int c = -Tc; c < Ac + Tc; c++) { P[r+Tr][c+Tc+1] += P[r+Tr][c+Tc] + is_taken(r, c + Tc) - is_taken(r, c); } } for (int c = -Tc; c < Ac + Tc; c++) { for (int r = -Tr; r < Ar + Ar; r++) { Q[r+Tr+1][c+Tc] += Q[r+Tr][c+Tc] + P[r+Tr+Tr][c+Tc] - P[r+Tr][c+Tc]; } } } bool free_tile(int sx, int sy) { return Q[sx+Tr][sy+Tc] == 0; } long tiles_needed_for(int dx, int dy) { long taken = 0; debug("dx=%d dy=%d => ", dx,dy); for (int qx = -dx; qx < Ar; qx+=Tr) { int min=-1, max=-1; for (int qy = -dy; qy < Ac; qy+=Tc) { if (!free_tile(qx,qy)) { taken += 1; debug("(%d,%d) ", qx,qy); } } } debug(" ---> %ld\n", taken); return taken; } void debug_R_Q() { debug("vstup: \n"); for (int r=-Tr; r<Ar+Tr; r++) { for (int c = -Tc; c<Ac+Tc; c++) { debug(" %c ", is_taken(r,c) ? 'X' : '.'); } debug("\n"); } debug("\n"); debug("P: \n"); for (int r=-Tr; r<Ar+Tr; r++) { for (int c = -Tc; c<Ac+Tc; c++) { if (!P[r+Tr][c+Tc]) { debug(" . "); } else { debug("%02d ", P[r+Tr][c+Tc]); } } debug("\n"); } debug("\n"); debug("Q: \n"); for (int r=-Tr; r<Ar+Tr; r++) { for (int c = -Tc; c<Ac+Tc; c++) { if (!Q[r+Tr][c+Tc]) { debug(" . "); } else { debug("%02d ", Q[r+Tr][c+Tc]); } } debug("\n"); } debug("\n"); } void solve() { build(); debug_R_Q(); long best = -1; for (int dx = 0; dx < Tr; dx++) { for (int dy = 0; dy < Tc; dy++) { long tiles = tiles_needed_for(dx, dy); if (best == -1 || best > tiles) { best = tiles; } } } printf("%ld\n", best); } int main() { while (true) { if (scanf("%d%d%d%d",&Ar,&Ac,&Tr,&Tc) != 4) break; for (int i = 0; i < Ar; i++) { char line[10000]; scanf("%s", line); for (int j=0;j<Ac;j++) { TAKEN[i][j] = line[j] == 'X'; } } solve(); } return 0; }
--- c5.s896.cteam032.fm.cpp.0.fm.cpp +++ c5.s898.cteam032.fm.cpp.0.fm.cpp @@ -14,6 +14,6 @@ using namespace std; -#define debug printf -//#define debug blackhole +//#define debug printf +#define debug blackhole void blackhole(...) {}