Go to diff to previous submission
#include <algorithm> #include <cctype> #include <cmath> #include <complex> #include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> using namespace std; #define DEBUG(x) cout << ">>> " << #x << " : " << x << endl; #define REP(i,a) for (int i = 0; i < (a); ++i) #define FOR(i,a,b) for (int i = (a); i <= (b); ++i) #define FORD(i,a,b) for (int i = (a); i >= (b); --i) inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; } const int INF = 1<<29; typedef long long ll; const int MAXN = 1400; bool input[MAXN][MAXN]; bool rowmax[MAXN][MAXN]; bool cellmax[MAXN][MAXN]; int AR, AC, TR, TC; int main() { while (scanf("%d%d%d%d ", &AR, &AC, &TR, &TC) == 4) { REP(r,MAXN) REP(c,MAXN) { input[r][c] = false; rowmax[r][c] = false; cellmax[r][c] = false; } REP(i,AR) { char *line = 0; size_t size; getline(&line, &size, stdin); REP(j,AC) input[i][j] = (line[j] == 'X'); free(line); } REP(r,AR) { int sum = 0; int begin = -TC; int end = 0; while (end < AC+TC) { if (begin >= 0) sum -= input[r][begin]; sum += input[r][end]; rowmax[r][end] = (sum > 0); ++begin; ++end; } } REP(c,AC+TC) { int sum = 0; int begin = -TR; int end = 0; while (end < AR+TR) { if (begin >= 0) sum -= rowmax[begin][c]; sum += rowmax[end][c]; cellmax[end][c] = (sum > 0); ++begin; ++end; } } int best = INF; REP(sc,TC) REP(sr,TR) { int cnt = 0; int r = sr; while (r < AR+TR) { int c = sc; while (c < AC+TC) { cnt += (cellmax[r][c] ? 1 : 0); c += TC; } r += TR; } if (cnt < best) best = cnt; } printf("%d\n", best); } return 0; }
--- c5.s797.cteam010.fm.cpp.0.fm.cpp +++ c5.s827.cteam010.fm.cpp.0.fm.cpp @@ -36,9 +36,13 @@ int main() { while (scanf("%d%d%d%d ", &AR, &AC, &TR, &TC) == 4) { + REP(r,MAXN) REP(c,MAXN) { + input[r][c] = false; + rowmax[r][c] = false; + cellmax[r][c] = false; + } REP(i,AR) { char *line = 0; size_t size; getline(&line, &size, stdin); - DEBUG(line); REP(j,AC) input[i][j] = (line[j] == 'X'); free(line); @@ -78,7 +82,4 @@ r += TR; } - DEBUG(sc); - DEBUG(sr); - DEBUG(cnt); if (cnt < best) best = cnt; }