Hướng dẫn giải của Bảo vệ bờ biển
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhậpTác giả: , , ,
Hiểu bài toán
Bài toán yêu cầu tính tổng diện tích mà các cột hải đăng quan sát được trên một lưới N x M. Mỗi cột hải đăng (giá trị 1) quan sát được ô nó đứng và 8 ô xung quanh (trong phạm vi lưới). Ta cần đếm t tổng số ô khác nhau được quan sát bởi ít nhất một cột hải đăng.
Các cách tiếp cận
Cách Sử dụng ma trận đánh dấu (Marking Matrix)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int a[1005][1005];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
// Dùng mảng a để đánh dấu trực tiếp
// 0: không có gì
// 1: có cột hải đăng
// 2: bị quan sát bởi cột hải đăng
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == 1) {
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
int x = i + dx;
int y = j + dy;
if (x >= 0 && x < n && y >= 0 && y < m) {
if (a[x][y] == 0)
a[x][y] = 2;
}
}
}
}
}
}
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (a[i][j] >= 1) ans++;
cout << ans;
return 0;
}
- Time Complexity: O(N * M)
- Space Complexity: O(N * M)
Cách tiếp cận này sử dụng ma trận đầu vào để đánh dấu các ô đã bị quan sát. Khi duyệt qua một ô có cột hải đăng (giá trị 1), ta đánh dấu các ô xung quanh bằng giá trị 2 (nếu ô đó đang là 0). Cuối cùng, ta đếm tất cả các ô có giá trị >= 1. Phương pháp này tận dụng bộ nhớ sẵn có nhưng thay đổi giá trị của ma trận đầu vào.
Cách Sử dụng ma trận đánh dấu phụ (Auxiliary Matrix)
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
vector<vector<int>> b(n, vector<int>(m, 0)); // Ma trận đánh dấu phụ
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == 1) {
// Đánh dấu 9 ô quanh cột hải đăng
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
int ni = i + dx;
int nj = j + dy;
if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
b[ni][nj] = 1;
}
}
}
}
}
}
int dem = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (b[i][j] == 1) dem++;
cout << dem;
return 0;
}
- Time Complexity: O(N * M)
- Space Complexity: O(N * M)
Ta tạo một ma trận phụ 'b' với kích thước N x M, khởi tạo tất cả các ô bằng 0. Khi gặp cột hải đăng, ta đánh dấu các ô tương ứng trong ma trận 'b' thành 1. Cuối cùng, chỉ cần đếm các ô có giá trị 1 trong ma trận 'b'. Cách này an toàn hơn vì không làm thay đổi dữ liệu đầu vào và dễ debug hơn.
Cách Tối ưu với mảng đánh dấu và đếm trực tiếp (Dùng mảng 1 chiều)
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
// Dùng mảng 1 chiều đánh dấu theo hàng
vector<int> marked(m, 0);
vector<vector<int>> input(n, vector<int>(m));
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> input[i][j];
}
}
int total = 0;
vector<int> current_marked(m, 0);
for (int i = 0; i < n; i++) {
fill(current_marked.begin(), current_marked.end(), 0);
for (int j = 0; j < m; j++) {
if (input[i][j] == 1) {
for (int dj = -1; dj <= 1; dj++) {
int col = j + dj;
if (col >= 0 && col < m) {
current_marked[col] = 1;
if (i > 0) marked[col] = 1;
if (i < n - 1) {
// Đánh dấu hàng dưới (cần lưu lại)
// Giải pháp này phức tạp khi dùng 1D array
}
}
}
}
}
// Đếm hàng hiện tại và cập nhật tổng
// (Code này minh họa ý tưởng, thực tế việc dùng 2D matrix là tối ưu nhất về độ phức tạp)
}
// Lưu ý: Code này chỉ minh họa ý tưởng, cách thông thường vẫn là dùng 2D matrix.
return 0;
}
- Time Complexity: O(N * M)
- Space Complexity: O(M)
Nếu N rất lớn và M nhỏ, ta có thể tối ưu bộ nhớ bằng cách chỉ lưu trữ trạng thái đánh dấu cho các hàng liên quan (hàng trước, hiện tại, hàng sau). Tuy nhiên, với giới hạn N, M <= 1000, việc dùng ma trận 2 chiều (O(N*M) bộ nhớ) là hoàn toàn chấp nhận được và dễ thực hiện hơn.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N * M) | O(N * M) | Sử dụng ma trận đánh dấu (Marking Matrix) |
| 2 | O(N * M) | O(N * M) | Sử dụng ma trận đánh dấu phụ (Auxiliary Matrix) |
| 3 | O(N * M) | O(M) | Tối ưu với mảng đánh dấu và đếm trực tiếp (Dùng mảng 1 chiều) |
Bài học kinh nghiệm
- Bài toán có thể giải quyết bằng cách mô phỏng lại quá trình quan sát: duyệt qua từng ô, nếu thấy cột hải đăng thì 'bảo' rằng các ô xung quanh đã được quan sát.
- Cần phân biệt giữa việc 'đếm số ô được quan sát' (tính cả trùng lặp) và 'tính diện tích được quan sát' (không tính trùng lặp). Đề bài yêu cầu tính diện tích (không trùng lặp), nên cần một cơ chế đánh dấu (visited/seen).
- Tránh đếm chéo: Nếu chỉ dùng mảng boolean hoặc đánh dấu, ta phải đảm bảo rằng một ô được đánh dấu là 1 lần dù bị nhiều cột cùng quan sát.
Lỗi thường gặp
- Lỗi truy cập mảng ngoài biên (out-of-bounds) khi kiểm tra các ô xung quanh cột hải đăng ở mép lưới. Cần kiểm tra điều kiện
0 <= x < nvà0 <= y < mtrước khi truy cập. - Nếu dùng mảng đánh dấu chung (ví dụ đánh dấu bằng số 2), phải cẩn thận không nhầm lẫn với các cột hải đăng mới ở các bước xử lý tiếp theo nếu logic không tách biệt rõ ràng.
- Quên xử lý trường hợp các cột hải đăng nằm gần nhau dẫn đến việc đếm trùng lặp nếu không dùng mảng đánh dấu.
Bình luận