Submission #3430658

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); }

constexpr int inf = 1e9;
template<class T> struct edge { int to; T cap; int rev; edge(int t, T c, int r) : to(t), cap(c), rev(r) {} };

void add_edge(int from, int to, auto cap, auto& g) {
  g[from].emplace_back(to, cap, g[to].size());
  g[to].emplace_back(from, 0, g[from].size() - 1);
}

template<class T> T dinic(int s, int t, VV< edge<T> > g) {
  int n = g.size();
  V<> dist, i;

  auto bfs = [&]() {
    dist.assign(n, -1);
    queue<int> q;
    dist[s] = 0; q.push(s);
    while (!q.empty()) {
      int v = q.front(); q.pop();
      for (auto&& e : g[v]) if (dist[e.to] == -1 and e.cap > 0) {
        dist[e.to] = dist[v] + 1; q.push(e.to);
      }
    }
  };

  auto dfs = [&](int v, T f, auto dfs) {
    if (v == s) return f;
    for (; i[v] < g[v].size(); i[v]++) {
      edge<T>& e = g[v][i[v]];
      if (dist[e.to] < dist[v] and g[e.to][e.rev].cap > 0) {
        T d = dfs(e.to, min(f, g[e.to][e.rev].cap), dfs);
        if (d > 0) {
          g[e.to][e.rev].cap -= d;
          e.cap += d;
          return d;
        }
      }
    }
    return (T) 0;
  };

  T res = 0;
  while (true) {
    bfs();
    if (dist[t] == -1) return res;
    i.assign(n, 0);
    while (true) {
      T f = dfs(t, inf, dfs);
      if (f == 0) break;
      res += f; 
    }
  }
}

int main() {
  cin.tie(NULL); ios::sync_with_stdio(false);
  int h, w; cin >> h >> w;
  V<string> a(h); for (int i = 0; i < h; i++) cin >> a[i];
  int s, t;
  for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
    if (a[i][j] == 'S') s = 2 * (i * w + j) + 1;
    if (a[i][j] == 'T') t = 2 * (i * w + j);
  }
  VV< edge<int> > g(2 * h * w);
  for (int i = 0; i < h; i++) {
    for (int jl = 0; jl < w; jl++) for (int jr = 0; jr < w; jr++) {
      if (jl != jr and a[i][jl] != '.' and a[i][jr] != '.') add_edge(2 * (i * w + jl) + 1, 2 * (i * w + jr), inf, g);
    }
  }
  for (int j = 0; j < w; j++) {
    for (int il = 0; il < h; il++) for (int ir = 0; ir < h; ir++) {
      if (il != ir and a[il][j] != '.' and a[ir][j] != '.') add_edge(2 * (il * w + j) + 1, 2 * (ir * w + j), inf, g);
    }
  }
  for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) add_edge(2 * (i * w + j), 2 * (i * w + j) + 1, 1, g);
  int res = dinic<int>(s, t, g);
  cout << (res >= inf ? -1 : res) << '\n';
}

Submission Info

Judge Result