#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<string> grid(n);
for (int i = 0; i < n; ++i) {
cin >> grid[i];
}
// dp_full[i][j]: hình vuông lớn nhất gồm '.' hoặc '#' kết thúc tại (i, j)
// dp_dot[i][j]: hình vuông lớn nhất gồm '.' kết thúc tại (i, j)
vector<vector<int>> dp_full(n, vector<int>(m, 0));
vector<vector<int>> dp_dot(n, vector<int>(m, 0));
long long total_diamonds = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
// Tính toán cho dp_full
if (grid[i][j] == '.' || grid[i][j] == '#') {
if (i > 0 && j > 0) {
dp_full[i][j] = 1 + min({dp_full[i - 1][j], dp_full[i][j - 1], dp_full[i - 1][j - 1]});
} else {
dp_full[i][j] = 1;
}
}
// Tính toán cho dp_dot
if (grid[i][j] == '.') {
if (i > 0 && j > 0) {
dp_dot[i][j] = 1 + min({dp_dot[i - 1][j], dp_dot[i][j - 1], dp_dot[i - 1][j - 1]});
} else {
dp_dot[i][j] = 1;
}
}
// Mỗi hình vuông full lớn hơn hình vuông dot tương ứng sẽ tạo ra một biên
// kim cương hợp lệ.
total_diamonds += dp_full[i][j] - dp_dot[i][j];
}
}
cout << total_diamonds << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Bài toán này không có đa test case trong input
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |