Submission #2161432


Source Code Expand

Copy
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<(n);i++)
#define loop(i,a,n) for(i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;


struct Bipartite_Matching
{
  vector< vector< int > > graph;
  vector< int > match, alive, used;
  int timestamp;
 
  Bipartite_Matching(int n)
  {
    timestamp = 0;
    graph.resize(n);
    alive.assign(n, 1);
    used.assign(n, 0);
    match.assign(n, -1);
  }
 
  void add_edge(int u, int v)
  {
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
 
  bool dfs(int v)
  {
    used[v] = timestamp;
    for(int i = 0; i < graph[v].size(); i++) {
      int u = graph[v][i], w = match[u];
      if(alive[u] == 0) continue;
      if(w == -1 || (used[w] != timestamp && dfs(w))) {
        match[v] = u;
        match[u] = v;
        return (true);
      }
    }
    return (false);
  }
 
  int bipartite_matching()
  {
    int ret = 0;
    for(int i = 0; i < graph.size(); i++) {
      if(alive[i] == 0) continue;
      if(match[i] == -1) {
        ++timestamp;
        ret += dfs(i);
      }
    }
    return (ret);
  } 
};


int main(){
  int i,j;
  int r,c;
  cin>>r>>c;
  vs s(r);
  rep(i,r)cin>>s[i];
  int sum=0;
  rep(i,r)rep(j,c)if(s[i][j]=='.')sum++;

  Bipartite_Matching flow(r*c);

  rep(i,r)rep(j,c)if(s[i][j]=='.'){
    if(i>0 && s[i-1][j]=='.')
        flow.add_edge((i-1)*c+j, i*c+j);
    if(j>0 && s[i][j-1]=='.')
        flow.add_edge(i*c+j-1, i*c+j);
  }

  cout << sum - flow.bipartite_matching() << endl;
  
}

Submission Info

Submission Time
Task C - 広告
User rika0384
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2080 Byte
Status
Exec Time 2 ms
Memory 384 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample0.txt, sample1.txt, sample2.txt, sample3.txt
All 400 / 400 01-00.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, sample0.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
01-00.txt 1 ms 256 KB
01-01.txt 2 ms 384 KB
01-02.txt 1 ms 256 KB
01-03.txt 1 ms 384 KB
01-04.txt 2 ms 384 KB
01-05.txt 1 ms 384 KB
01-06.txt 2 ms 384 KB
01-07.txt 1 ms 256 KB
01-08.txt 2 ms 384 KB
01-09.txt 2 ms 384 KB
01-10.txt 2 ms 384 KB
01-11.txt 1 ms 256 KB
01-12.txt 2 ms 384 KB
01-13.txt 2 ms 384 KB
01-14.txt 1 ms 384 KB
01-15.txt 2 ms 384 KB
01-16.txt 1 ms 256 KB
sample0.txt 1 ms 256 KB
sample1.txt 1 ms 256 KB
sample2.txt 1 ms 256 KB
sample3.txt 1 ms 256 KB