Analysis: Figure Eight by Nathan Pinsker
/* LANG: C++ */ #includeYou can also reduce the memory requirements to O(N^2), although it was not required. Here is Mark Gordon's solution demonstrating this:#include using namespace std; #define NMAX 200 int n; bool grid[NMAX][NMAX]; int rowcmp[NMAX][NMAX]; short best_down[NMAX][NMAX][NMAX]; short best_up[NMAX][NMAX][NMAX]; short best_up_total[NMAX][NMAX][NMAX]; int main() { #ifndef HOME freopen("eight.in", "r", stdin); freopen("eight.out", "w", stdout); #endif scanf("%d", &n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { char c; do { c = fgetc(stdin); } while (c != '.' && c != '*'); grid[i][j] = (c == '.'); } } int rcmp = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (!grid[i][j]) { rcmp++; } rowcmp[i][j] = rcmp; } } for (int i = 0; i < n; i++) { for (int j1 = 0; j1 < n; j1++) { bool okay = grid[i][j1]; for (int j2 = j1 + 1; j2 < n; j2++) { okay = okay && grid[i][j2]; if (grid[i][j1] && grid[i][j2]) { if (i > 0 && best_up[i-1][j1][j2] != -1) { best_up[i][j1][j2] = 1 + best_up[i-1][j1][j2]; } else { best_up[i][j1][j2] = okay ? 0 : -1; } } else { best_up[i][j1][j2] = -1; } } } } for (int i = n-1; i >= 0; i--) { for (int j1 = 0; j1 < n; j1++) { bool okay = grid[i][j1]; for (int j2 = j1 + 1; j2 < n; j2++) { okay = okay && grid[i][j2]; if (grid[i][j1] && grid[i][j2]) { if (i < n-1 && best_down[i+1][j1][j2] != -1) { best_down[i][j1][j2] = 1 + best_down[i+1][j1][j2]; } else { best_down[i][j1][j2] = okay ? 0 : -1; } } else { best_down[i][j1][j2] = -1; } } } } long long ans = 0; for (int i = 0; i < n; i++) { for (int l = 1; l < n; l++) { for (int j1 = 0; j1 + l < n; j1++) { int j2 = j1 + l; if (grid[i][j1] && grid[i][j2]) { best_up_total[i][j1][j2] = (best_up[i][j1][j2] < 2 ? -1 : (best_up[i][j1][j2] - 1) * (j2 - j1 - 1)); if (l > 1) { best_up_total[i][j1][j2] = max(best_up_total[i][j1][j2], max(best_up_total[i][j1+1][j2], best_up_total[i][j1][j2-1])); } } else { best_up_total[i][j1][j2] = -1; } if (rowcmp[i][j1] == rowcmp[i][j2] && best_up_total[i][j1][j2] != -1 && best_down[i][j1][j2] >= 2) { ans = max(ans, (long long) best_up_total[i][j1][j2] * (long long) (best_down[i][j1][j2] - 1) * (long long) (j2 - j1 - 1)); } } } } printf("%lld\n", ans); }
/* LANG: C++ */ #include#include #include using namespace std; #define MAXN 300 string A[MAXN]; bool B[MAXN][MAXN]; int DP[MAXN][MAXN]; int DPO[MAXN][MAXN]; int main() { freopen("eight.in", "r", stdin); freopen("eight.out", "w", stdout); int N; cin >> N; for(int i = 0; i < N; i++) { cin >> A[i]; } for(int i = 0; i + 1 < N; i++) { for(int j = 0; j < N; j++) { B[i][j] = A[j][i] == '.' && A[j][i + 1] == '.'; } } long long result = 0; for(int sz = 3; sz <= N; sz++) { memcpy(DPO, DP, sizeof(DP)); for(int i = 0; i + sz <= N; i++) { int mn = N; for(int j = 0; j < N; j++) { B[i][j] = B[i][j] && A[j][i + sz - 1] == '.'; if(B[i][j]) { mn = min(mn, j); } } int pr = -1, tpr = -1; int mx = mn; for(int j = mn; j < N; j++) { for(mx = max(mx, j); mx < N && A[mx][i] == '.' && A[mx][i + sz - 1] == '.'; mx++) { if(B[i][mx]) { tpr = mx; } } if(B[i][j]) { DP[i][j] = max(DPO[i][j], DPO[i + 1][j]); if(pr == -1) { pr = j; } else { DP[i][j] = max(DP[i][j], max(0, j - pr - 1) * (sz - 2)); } long long r = (long long)DP[i][j] * max(0, tpr - j - 1) * (sz - 2); result = max(result, r); } else if(A[j][i] != '.' || A[j][i + sz - 1] != '.') { pr = -1; } } } } cout << (result == 0 ? -1 : result) << endl; return 0; }