1 条题解
-
0
#include <bits/stdc++.h> using namespace std; int n, m; int g[505][505]; int sum[505][505]; int getSum(int u, int d, int l, int r) { return sum[d][r] - sum[d][l - 1] - sum[u - 1][r] + sum[u - 1][l - 1]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { char c; cin >> c; g[i][j] = (c == '#'); } for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + g[i][j]; long long ans = 0; for (int u = 1; u <= n; u++) for (int d = u; d <= n; d++) { for (int l = 1, r = l - 1; l <= m; l++) { // 把 r 调整到第一个符合要求的位置。 // l~r 就都符合要求 for (; r + 1 <= m && getSum(u, d, l, r + 1) <= 1; r++) ; ans += r - l + 1; } } cout << ans << "\n"; return 0; }
- 1
信息
- ID
- 108
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 8
- 标签
- 递交数
- 53
- 已通过
- 9
- 上传者