Submission #1246763

#TimeUsernameProblemLanguageResultExecution timeMemory
1246763vht2025Dijamant (COCI22_dijamant)C++20
0 / 70
0 ms392 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...