Untitled
unknown
c_cpp
a year ago
3.3 kB
4
Indexable
Never
#include<bits/stdc++.h> #define endl '\n' #define int long long #define pii pair<int, int> #define INF 0x3f3f3f3f3f3f3f3f #define PB push_back #define SZ(x) (int)x.size() using namespace std; const int MXN = 2e5 + 5; int r, c, d; bool vis[50][50]; char arr[50][50]; int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1}; vector<pii> S, P, H; bool in(int x, int y){ return (0<=x && x<r && 0<=y && y<c); } void bfs(pii st){ queue<pii> q; q.push(st); vis[st.first][st.second] = 1; while(!q.empty()){ pii now = q.front(); q.pop(); for(int i=0; i<4; i++){ int xx = now.first + dx[i], yy = now.second + dy[i]; if(in(xx, yy) && !vis[xx][yy]){ vis[xx][yy] = 1; if(arr[xx][yy] == '.') q.push({xx, yy}); } } } } struct Dinic{ struct Edge{ int v,f,re; }; int n,s,t,level[MXN]; vector<Edge> E[MXN]; void init(int _n, int _s, int _t){ n = _n; s = _s; t = _t; for (int i=0; i<n; i++) E[i].clear(); } void add_edge(int u, int v, int f){ E[u].PB({v,f,SZ(E[v])}); E[v].PB({u,0,SZ(E[u])-1}); } bool BFS(){ for (int i=0; i<n; i++) level[i] = -1; queue<int> que; que.push(s); level[s] = 0; while (!que.empty()){ int u = que.front(); que.pop(); for (auto it : E[u]){ if (it.f > 0 && level[it.v] == -1){ level[it.v] = level[u]+1; que.push(it.v); } } } return level[t] != -1; } int DFS(int u, int nf){ if (u == t) return nf; int res = 0; for (auto &it : E[u]){ if (it.f > 0 && level[it.v] == level[u]+1){ int tf = DFS(it.v, min(nf,it.f)); res += tf; nf -= tf; it.f -= tf; E[it.v][it.re].f += tf; if (nf == 0) return res; } } if (!res) level[u] = -1; return res; } int flow(int res=0){ while ( BFS() ) res += DFS(s,2147483647); return res; } }flow; void solve(){ cin >> r >> c >> d; for(int i=0; i<r; i++){ for(int j=0; j<c; j++){ cin >> arr[i][j]; if(arr[i][j] == 'S') S.push_back({i, j}); else if(arr[i][j] == 'P') P.push_back({i, j}); else if(arr[i][j] == 'H') H.push_back({i, j}); } } int s = S.size(), h = H.size(), p = P.size(); flow.init(s+2*h+p+2, 0, s+2*h+p+1); for(int i=0; i<H.size(); i++){ flow.add_edge(s+i+1, s+h+i+1, 1); } for(int i=0; i<s; i++){ memset(vis, 0, sizeof(vis)); bfs(S[i]); for(int j=0; j<h; j++){ if(vis[H[j].first][H[j].second]) flow.add_edge(i+1, s+j+1, 1); } flow.add_edge(0, i+1, 1); } for(int i=0; i<P.size(); i++){ memset(vis, 0, sizeof(vis)); bfs(P[i]); for(int j=0; j<h; j++){ if(vis[H[j].first][H[j].second]) flow.add_edge(s+h+j+1, s+2*h+i+1, 1); } flow.add_edge(s+2*h+i+1, s+2*h+p+1, 1); } cout << flow.flow() << endl; } signed main(){ ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T = 1; // cin >> T; while(T--){ solve(); } }