http://arc074.contest.atcoder.jp/tasks/arc074_d
flow。
行と列を代表する頂点を用意してうまく辺を張ると、辺の本数がO(H*W)になって十分高速。
int H, W; string S[MAX_N]; void solve() { cin >> H >> W; int s, t; rep(i, 0, H) { cin >> S[i]; rep(j, 0, W) { int id = i * W + j; if(S[i][j] == 'S') { s = id * 2 + 1; } if(S[i][j] == 'T') { t = id * 2; } if(S[i][j] != '.') { add_edge(id * 2, id * 2 + 1, 1); add_edge(id * 2 + 1, H * W * 2 + j, inf); add_edge(H * W * 2 + j, id * 2, inf); add_edge(id * 2 + 1, H * W * 2 + i + W, inf); add_edge(H * W * 2 + i + W, id * 2, inf); } } } int res = max_flow(s, t); if(res >= inf) cout << "-1\n"; else cout << res << "\n"; }
フローの計算量の見積もり方がよくわからない…