Submission #3422284

---

Source Code Expand

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A&lang=jp
#include<bits/stdc++.h>
#pragma warning(disable:4996)
#ifdef _MSC_VER
#  define __builtin_popcount __popcnt
#endif
#define int long long
using namespace std;
using ll = long long;
using ld = long double;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
inline void my_io() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	cout << fixed << setprecision(10);
}
int h, w;
vector<vector<int>>v;
int INF = 1000000;
struct edge {
	int from, to, cap, rev;//revは逆辺のindex  to:行き先,cap:容量,rev:逆(G[e.to][e.rev]で逆辺の構造体にアクセスできる。)
};

vector<vector<edge>>g;
vector<bool>used;
void add_edge(int from, int to, int cap) {
	g[from].push_back(edge{ from, to, cap, (int)g[to].size() });//g[to].size()で次の行で取得される
	g[to].push_back(edge{ to, from, 0, (int)g[from].size() - 1 });
}
int dfs(int v, int t, int f) {//vからtに流せる最大
	if (v == t) {//終点までたどり着いたら
		return f;
	}
	used[v] = true;
	for (int i = 0; i < g[v].size(); i++) {
		edge &e = g[v][i];//今見ている頂点から伸びている辺を参照している(コピーではない！！)
		if (!used[e.to] && e.cap>0) {//その辺の行き先をまだ調べていなくて、辺の容量にも余裕がある
			int d = dfs(e.to, t, min(f, e.cap));//capを超えない目一杯を流す
			if (d > 0) {//流しているなら
				e.cap -= d;//流した分capから引く
				g[e.to][e.rev].cap += d;//流した分逆辺のcapを増やす
				return d;
			}

		}

	}
	return 0;//何も流せなかった
}
int max_flow(int s, int t) {//sからtへの最大流
	int flow = 0;
	for (;;) {
		for (int i = 0; i<used.size(); i++) {
			used[i] = false;
		}
		int f = dfs(s, t, numeric_limits<signed>::max());
		if (f == 0) {
			return flow;//もう何も流せないので今まで流した量の和を返す
		}
		flow += f;
	}

}
signed main(){
	my_io();
	cin >> h >> w;
	v.resize(h);
	g.resize(h*w);
	used.resize(h*w);
	int sx, sy, gx, gy;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			char ch;
			cin >> ch;
			v[i].push_back(ch);
			if (ch == 'S') {
				sx = i;
				sy = j;
			}
			else if (ch == 'T') {
				gx = i;
				gy = j;
			}
		}
	}
	//横の辺を張る
	for (int i = 0; i < h; i++) {
		vector<int>vertex;//頂点を持っておくvector
		for (int j = 0; j < w; j++) {
			if (v[i][j] == 'S' || v[i][j] == 'o'||v[i][j]=='T') {
				vertex.push_back(j);
			}
		}
		for (int k = 0; k < vertex.size(); k++) {
			for (int l = 0; l < vertex.size(); l++) {
				if (k != l) {
					if (v[i][vertex[k]] == 'S'&& v[i][vertex[l]] == 'T') {
						add_edge(i*w + vertex[k], i*w + vertex[l], INF);
						add_edge(i*w + vertex[l], i*w + vertex[k], INF);
					}
					else if(v[i][vertex[k]] == 'o' && v[i][vertex[l]] == 'o'|| v[i][vertex[k]] == 'S' && v[i][vertex[l]] == 'o'|| v[i][vertex[k]] == 'T' && v[i][vertex[l]] == 'o'){
						add_edge(i*w + vertex[k], i*w + vertex[l], 1);
						add_edge(i*w + vertex[l], i*w + vertex[k], 1);
					}
				}
			}
		}
	}
	//縦の辺を張る
	for (int j = 0; j < w; j++) {
		vector<int>vertex;
		for (int i = 0; i < h; i++) {
			if (v[i][j] == 'S' || v[i][j] == 'o'||v[i][j]=='T') {
				vertex.push_back(i);
			}
		}
		for (int k = 0; k < vertex.size(); k++) {
			for (int l = 0; l < vertex.size(); l++) {
				if (k != l) {
					if (v[vertex[k]][j] == 'S'&& v[vertex[l]][j] == 'T') {
						add_edge( vertex[k]*w+j,vertex[l]*w+j, INF);
						add_edge(vertex[l] * w + j, vertex[k] * w + j, INF);
					}
					else if(v[vertex[k]][j] == 'o' && v[vertex[l]][j] == 'o' || v[vertex[k]][j] == 'S' && v[vertex[l]][j] == 'o' || v[vertex[k]][j] == 'T' && v[vertex[l]][j] == 'o'){
						add_edge(vertex[k] * w + j, vertex[l] * w + j, 1);
						add_edge(vertex[l] * w + j, vertex[k] * w + j, 1);
					}
				}
			}
		}
	}
	int ans = max_flow(sx*w + sy, gx*w + gy);
	if (ans>=INF) {
		cout << -1 << endl;
	}
	else cout << ans<< endl;
	return 0;
}
/*
10 10
.o...o..o.
....o.....
....oo.oo.
..oooo..o.
....oo....
..o..o....
o..o....So
o....T....
....o.....
........oo
*/
//5

Submission Info

Judge Result