Untitled

#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;
int 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();
        int v = vis[now.first][now.second];
        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] = v + 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++){
            int vv = vis[H[j].first][H[j].second];
            if(0 < vv && vv <= d)
                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++){
            int vv = vis[H[j].first][H[j].second] - 1;
            if(0 < vv && vv <= d)
                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();
    }
}