- 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**
zt09nguyenhoangnhatanh
Created at
2 likes