- Tư tưởng: Ta sẽ coi những khu vực bị các quân cờ đen bao vây là những vùng liên thông riêng biệt
- Do quân trắng chỉ bị ăn khi bốn phía xung quanh nó không có ô trống nên ta chỉ cần kiểm tra tính hợp lệ của vùng liên thông (không có ô trống nào xuất hiện trong vùng liên thông) đồng thời đếm số quân trắng trong vùng liên thông đó nếu nó hợp lệ
- Cách làm: Nếu phát hiện ô chưa thăm khác ô $B$, thực hiện BFS từ ô đấy và đếm số lượng ký tự $W$ trong quá trình BFS rồi lưu vào mảng ans. Tuy nhiên trong quá trình BFS nếu phát hiện ký tự $.$ thì không lưu
- Kết quả là tổng số quân trắng trong các vùng liên thông hợp lệ
Code (C++):
#include <bits/stdc++.h>
#define ll long long
#define mpi make_pair
using namespace std;
const int N =501;
vector<pair<ll,ll>>v = {{1,0},{-1,0},{0,1},{0,-1}};
char a[N][N];
bool vis[N][N];
vector<ll> ans;
ll n,m;
string s;
bool valid(ll i, ll j){
return ( i>= 1 && j >=1 && i<=n && j <= m && vis[i][j]==0 && a[i][j] != 'B');
}
void bfs(ll i, ll j){
ll cnt=0;
if(a[i][j]=='W'){
++cnt;
vis[i][j]=1;
}
queue<pair<ll,ll>>q;
q.push(mpi(i,j));
bool ck =1;
while(!q.empty()){
pair<ll,ll>u =q.front();
q.pop();
for(ll x=0;x<4;++x){
ll a_ = u.first + v[x].first, b =u.second + v[x].second;
if(valid(a_,b)){
vis[a_][b]=1;
if(a[a_][b] == 'W'){
++cnt;
}
else {
ck =0;
cnt = 0;
}
q.push(mpi(a_,b));
}
}
}
if(ck ==1 && cnt != 0) ans.push_back(cnt);
}
int main(){
cin >> n >> m;
for(ll i=1;i<=n;++i){
cin >> s;
s = " "+s;
for(ll j=1;j<=m;++j){
a[i][j]=s[j];
}
}
for(ll i=1;i<=n;++i){
for(ll j=1;j<=m;++j){
if(!vis[i][j] && a[i][j] != 'B') bfs(i,j);
}
}
cout << accumulate(ans.begin(),ans.end(),0) << '\n';
return 0;
}
**Lưu ý: Đây có thể chưa phải giải thuật tối ưu nhất cho bài toán. Không nhất thiết phải làm theo lời giải**
### Ý tưởng (có thể chưa phải tối ưu nhất):
Ta xem mỗi ô 'W' trên ma trận là một đỉnh trong đồ thị.
Nếu hai ô 'W' liền kề nhau (theo 4 hướng), ta tạo một cạnh nối hai đỉnh đó.
=> Bài toán trở thành: Duyệt các thành phần liên thông trong đồ thị, mỗi thành phần:
- Nếu có ít nhất một đỉnh thuộc loại "không thể bị ăn" (tức có ô trống '.' liền kề) thì bỏ qua, không tính vào biến đếm chính (kết quả).
- Ngược lại, cộng số đỉnh trong thành phần đó vào kết quả cuối cùng.
### Cách làm:
B1: Thiết lập:
+ Hàm: Hàm chuyển đổi chỉ số ma trận thành chỉ số đỉnh trong đồ thị; hàm bfs nhưng có thêm biến đếm phụ cho mỗi vùng liên thông, và biến kiểm tra có ô "không thể bị ăn" không; hàm duyệt các thành phần liên thông và có thêm biến đếm chính để trả về kết quả cuối cùng.
+ Danh sách kề: Tạo bằng vector <unordered_set <>> để phòng trường hợp bị trùng đỉnh.
+ Ma trận: Tạo bằng vector <vector <>> với kích cỡ (n+2)*(m+2) để tạo biên, tránh bị vượt quá chỉ số khi duyệt.
+ 1 vector để đánh dấu đỉnh có là "không thể bị ăn" không, set toàn bộ phần tử là '-1' ('B' hoặc ô trống).
B2: Nhập ma trận (theo đề là ở dạng chuỗi) rồi chuyển về dạng ma trận trong vector 2 chiều.
B3: Duyệt ma trận để kiểm tra: Nếu ô hiện tại là 'W':
+ Nếu ô liền kề cũng là 'W', tạo cạnh nối giữa 2 đỉnh đó trong đồ thị (dùng danh sách kề và hàm chuyển đổi chỉ số).
+ Nếu tồn tại ô trống '.' trong 4 ô liền kề, đánh dấu ô đó là '1', ngược lại đánh dấu là '0'
B4: Thực hiện hàm đếm vùng liên thông, mỗi lần bfs khi duyệt xong 1 đỉnh thì tăng biến đếm phụ;
+ Nếu trong khi duyệt có ô được đánh dấu '1' thì đánh dấu biến kiểm tra = 'true', khi đó biến đếm phụ sẽ không cộng vào biến đếm chính
+ Ngược lại, cộng biến đếm phụ vào biến đếm chính sau khi duyệt.
B5: Output biến đếm chính.
### Code (C++):
```
#include <bits/stdc++.h>
using namespace std;
long long n, m;
vector <long long> visited;
vector <unordered_set <long long>> dske;
vector <long long> ktra;
long long change (long long x, long long y) {
return (x - 1) * m + y;
} // Ham chuyen doi chi so
bool bfs (long long u, long long &tam) {
queue <long long> q;
q.push (u);
visited[u] = 1;
bool found = 0;
while (not q.empty ()) {
long long v = q.front ();
q.pop ();
if (ktra[v] == 0) found = 1;
++tam;
for (long long x : dske[v]) {
if (not visited[x]) {
visited[x] = 1;
q.push (x);
}
}
}
return found;
}
long long handle (long long x) {
long long dem = 0; // Bien dem chinh
for (long long i = 1; i <= x; ++i) {
if (not visited[i] and (ktra[i] > -1)) {
long long tam = 0; // Bien dem phu
if (not bfs (i, tam)) dem += tam;
}
}
return dem; // Tra ve ket qua
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
cin.ignore ();
vector <vector <char>> matran (n + 2, vector <char> (m + 2, 'B'));
for (long long i = 1; i <= n; ++i) {
string s;
getline (cin, s);
for (long long j = 1; j <= m; ++j) matran[i][j] = s[j - 1];
}
dske.resize(change (n, m) + 1);
ktra.resize (change (n, m) + 1, -1);
for (long long i = 1; i <= n; ++i) {
for (long long j = 1; j <= m; ++j) {
if (matran[i][j] == 'W') {
if (matran[i + 1][j] == 'W') {
dske[change (i + 1, j)].insert (change (i, j));
dske[change (i, j)].insert (change (i + 1, j));
}
if (matran[i][j + 1] == 'W') {
dske[change (i, j + 1)].insert (change (i, j));
dske[change (i, j)].insert (change (i, j + 1));
}
if (matran[i - 1][j] == 'W') {
dske[change (i - 1, j)].insert (change (i, j));
dske[change (i, j)].insert (change (i - 1, j));
}
if (matran[i][j - 1] == 'W') {
dske[change (i, j - 1)].insert (change (i, j));
dske[change (i, j)].insert (change (i, j - 1));
}
if (matran[i + 1][j] == '.' or matran[i][j + 1] == '.' or matran[i - 1][j] == '.' or matran[i][j - 1] == '.') {
ktra[change (i, j)] = 0;
}
else ktra[change (i, j)] = 1;
}
}
}
visited.resize(change (n, m) + 1, 0);
cout << handle (change (n, m));
return 0;
}
```
(Lần đầu viết lời giải nên ý tưởng có thể chưa được "clear" lắm, mong mọi người thông cảm :>
zt09nguyenhoangnhatanh
Created at
3 likes
GiangCreeper09
Created at
1 likes