Go to diff to previous submission
/* 5 5 3 1 ..... .X... .XXX. .XXX. .XXX. 5 10 2 3 .......XX. .X....XX.. .XXX...... .XXX...... .XXX...... 3 3 3 3 XXX XXX XXX 3 3 2 2 XXX XXX XXX 3 3 2 2 XX. XXX XXX 17 32 5 9 ........XXXXXXXX................ ........XXXXXXXX................ ........XXXXXXXX................ ........XXXXXXXXX............... ........XXXXXXXXXXXXXXX......... ........XXXXXXXXXXXXXXXXXXXX.... ........XXXXXXXXXXXXXXXXXXXXX... XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.. ..XXXXXXXXXXXXXXXXXXXXXXXXXXXXX. ....XXXXXXXXXXXXXXXXXXXXXXXXXXX. ......XXXXXXXXXXXXXXXXXXXXXXXXX. ........XX..XXXXXXXXXXXXXXXXX... .............XXXXXXXXXXXXXX..... ...............XXXXXXXXX........ ................XXXXXXX......... .................XXXXX.......... ....................XXX......... */ #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 3000 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 + Ac; 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) { 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.s825.cteam032.fm.cpp.0.fm.cpp +++ c5.s845.cteam032.fm.cpp.0.fm.cpp @@ -1,2 +1,47 @@ +/* +5 5 3 1 +..... +.X... +.XXX. +.XXX. +.XXX. +5 10 2 3 +.......XX. +.X....XX.. +.XXX...... +.XXX...... +.XXX...... +3 3 3 3 +XXX +XXX +XXX +3 3 2 2 +XXX +XXX +XXX +3 3 2 2 +XX. +XXX +XXX +17 32 5 9 +........XXXXXXXX................ +........XXXXXXXX................ +........XXXXXXXX................ +........XXXXXXXXX............... +........XXXXXXXXXXXXXXX......... +........XXXXXXXXXXXXXXXXXXXX.... +........XXXXXXXXXXXXXXXXXXXXX... +XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.. +..XXXXXXXXXXXXXXXXXXXXXXXXXXXXX. +....XXXXXXXXXXXXXXXXXXXXXXXXXXX. +......XXXXXXXXXXXXXXXXXXXXXXXXX. +........XX..XXXXXXXXXXXXXXXXX... +.............XXXXXXXXXXXXXX..... +...............XXXXXXXXX........ +................XXXXXXX......... +.................XXXXX.......... +....................XXX......... + */ + #include <cstdio> #include <cstdlib> @@ -14,13 +59,15 @@ using namespace std; -//#define debug printf -#define debug blackhole +#define debug printf +//#define debug blackhole void blackhole(...) {} +#define MAXN 3000 + int Ar,Ac,Tr,Tc; -bool TAKEN[2000][2000]; // [Ar][Ac] +bool TAKEN[MAXN][MAXN]; // [Ar][Ac] -int P[2000][2000]; // !!! od -Tr, -Tc do Ar, Ac -int Q[2000][2000]; +int P[MAXN][MAXN]; // !!! od -Tr, -Tc do Ar, Ac +int Q[MAXN][MAXN]; inline int is_taken(int x, int y) { @@ -30,6 +77,6 @@ void build() { - for (int i=0;i<2000;i++) { - for (int j=0;j<2000;j++) { + for (int i=0;i<MAXN;i++) { + for (int j=0;j<MAXN;j++) { P[i][j] = 0; Q[i][j] = 0; }