Submission #1867935

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9;

struct MaxFlow {
	struct edge {
		int u; int v; int c; int f;
		edge(int u=0, int v=0, int c=0, int f=0): u(u), v(v), c(c), f(f) {}
	};

	int n, s, t; // nNode, source, sink
	vector< vector<int> > G;
	vector<edge> e;
	MaxFlow(int n=0, int s=0, int t=0): n(n), s(s), t(t) {
		G.assign(n + 1, vector<int>());
	}
	void add(int u, int v, int c) {
		G[u].push_back(e.size()); e.push_back(edge(u, v, c, 0));
		G[v].push_back(e.size()); e.push_back(edge(v, u, 0, 0));
	}

	vector<int> d; // dist
	vector<int> ptr; // pointer
	bool bfs() {
		d.assign(n + 1, -1); ptr.assign(n + 1, 0);
		queue <int> q; q.push(s); d[s] = 0;
		while(!q.empty()) {
			int u = q.front(); q.pop();
			for (int id : G[u]) if (d[e[id].v] == -1 && e[id].c > e[id].f) {
				d[e[id].v] = d[u] + 1;
				q.push(e[id].v);
			}
		}
		return d[t] != -1;
	}
	int dfs(int u, int fl) {
		if (!fl || u == t) return fl;
		for (int &i = ptr[u]; i < G[u].size(); ++i) {
			int id = G[u][i];
			if (e[id].f >= e[id].c || d[e[id].v] != d[u] + 1) continue;
			int nxt = dfs(e[id].v, min(fl, e[id].c - e[id].f));
			if (nxt) {
				e[id].f += nxt; e[id ^ 1].f -= nxt; return nxt;
			}
		}
		return 0;
	}
	int maxFlow() {
		int ans = 0;
		while(bfs()) {
			while(int cur = dfs(s, inf)) ans += cur;
		}
		return ans;
	}
} mf;

const int N = 105;
int H, W;
int st, en;
char a[N][N];
vector < pair<int,int> > cells;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> H >> W;
	for (int i = 1; i <= H; ++i) {
		for (int j = 1; j <= W; ++j) {
			cin >> a[i][j];
			if (a[i][j] != '.') cells.push_back(make_pair(i,j));
		}
	}
	for (int i = 0; i < cells.size(); ++i) {
		int x = cells[i].first, y = cells[i].second;
		if (a[x][y] == 'S') st = i;
		else if (a[x][y] == 'T') en = i;
	}

	// create Max Flow
	mf = MaxFlow(cells.size() * 2 + 10, 2 * st + 1, 2 * en);
	for (int i = 0; i < cells.size(); ++i) {
		int x = cells[i].first, y = cells[i].second;
		mf.add(2 * i, 2 * i + 1, 1);
		for (int j = 0; j < cells.size(); ++j) if (j != i) {
			if (cells[i].first == cells[j].first || cells[i].second == cells[j].second) {
				mf.add(2 * i + 1, 2 * j, inf);
			}
		}
	}

	// find mincut 
	int ans = mf.maxFlow();
	if (ans >= inf) printf("-1\n");
	else printf("%d\n", ans);
}

Submission Info

Judge Result