fork download
copy 
  1. #include <bits/stdc++.h>
  2. typedef long long ll;
  3. using namespace std;
  4. void Code_By_Mohamed_Khaled() {
  5.     ios_base::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.     cout.tie(nullptr);
  8. #ifndef ONLINE_JUDGE
  9.     freopen("input.txt","r",stdin);
  10.     freopen("output.txt","w",stdout);
  11. #endif
  12. }
  13. ll mod=1e9+7;
  14. ll add(ll a, ll b) { return ((a % mod) + (b % mod)) % mod; }
  15. ll mul(ll a, ll b) { return ((a % mod) * (b % mod)) % mod; }
  16. ll sub(ll a, ll b) { return ((a % mod) - (b % mod) + mod) % mod;}
  17. ll dx[]={-1,1,0,0};
  18. ll dy[]={0,0,-1,1};
  19. ll n,m;vector<string>v;
  20. vector<pair<ll,ll>>w,g;
  21. vector<vector<ll>>adj;
  22. vector<ll>match;vector<bool>vis;
  23. bool dfs(ll node) {
  24.     for (auto it:adj[node]) {
  25.         if (!vis[it]) {
  26.             vis[it]=true;
  27.             if (match[it]==-1 or dfs(match[it])) {
  28.                 match[it]=node;
  29.                 return true;
  30.             }
  31.         }
  32.     }
  33.     return false;
  34. }
  35. int main() {
  36.     Code_By_Mohamed_Khaled();
  37.     cin>>n>>m;
  38.     v.resize(n);
  39.     for (auto &it:v)cin>>it;
  40.     vector<vector<int>>idx(n,vector<int>(m,-1));
  41.     for (int i=0;i<n;i++){
  42.         for (int j=0;j<m;j++){
  43.             if(v[i][j]=='W'){
  44.                 w.push_back({i,j});
  45.             }
  46.             else if(v[i][j]=='G'){
  47.                 idx[i][j]=g.size();
  48.                 g.push_back({i, j});
  49.             }
  50.         }
  51.     }
  52.     adj.resize(w.size());
  53.     for (int i=0;i<w.size();i++){
  54.         int x=w[i].first,y=w[i].second;
  55.         for (int d = 0; d <4;d++){
  56.             int ii= x + dx[d],jj=y+dy[d];
  57.             if(ii>=0 and ii<n and jj>=0 and jj<m){
  58.                 if(v[ii][jj]=='G'){
  59.                     int id=idx[ii][jj];
  60.                     adj[i].push_back(id);
  61.                 }
  62.             }
  63.         }
  64.     }
  65.     match.assign(g.size(), -1);
  66.     ll cnt=0;
  67.     for (int i=0;i<w.size();i++){
  68.         vis.assign(g.size(),false);
  69.         if(dfs(i))cnt++;
  70.     }
  71.     cout<<cnt;
  72.     return 0;
  73. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/aeKHRm
language:
C++ (gcc 8.3)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!