#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define fi first
#define se second
#define pp push_back
#define all(x) (x).begin(), (x).end()
#define Ones(n) __builtin_popcount(n)
#define endl '\n'
#define mem(arrr, xx) memset(arrr,xx,sizeof arrr)
//#define int long long
#define debug(x) cout << (#x) << " = " << x << endl
void Gamal() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef Clion
freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}
int dx[] = {+0, +0, -1, +1, +1, +1, -1, -1};
int dy[] = {-1, +1, +0, +0, +1, -1, +1, -1};
const double EPS = 1e-9;
const ll OO = 0X3F3F3F3F3F3F3F3F;
const int N = 20 + 5, INF = INT_MAX, MOD = 1e9 + 7, LOG = 20;
struct edge
{
int from, to, cap, flow, index;
edge(int from, int to, int cap, int flow, int index):
from(from), to(to), cap(cap), flow(flow), index(index) {}
};
struct PushRelabel
{
int n;
vector<vector<edge> > g;
vector<long long> excess;
vector<int> height, active, count;
queue<int> Q;
PushRelabel(int n):
n(n), g(n), excess(n), height(n), active(n), count(2*n) {}
void addEdge(int from, int to, int cap)
{
g[from].push_back(edge(from, to, cap, 0, g[to].size()));
if(from==to)
g[from].back().index++;
g[to].push_back(edge(to, from, 0, 0, g[from].size()-1));
}
void enqueue(int v)
{
if(!active[v] && excess[v] > 0)
{
active[v]=true;
Q.push(v);
}
}
void push(edge &e)
{
int amt=(int)min(excess[e.from], (long long)e.cap - e.flow);
if(height[e.from]<=height[e.to] || amt==0)
return;
e.flow += amt;
g[e.to][e.index].flow -= amt;
excess[e.to] += amt;
excess[e.from] -= amt;
enqueue(e.to);
}
void relabel(int v)
{
count[height[v]]--;
int d=2*n;
for(auto &it:g[v])
{
if(it.cap-it.flow>0)
d=min(d, height[it.to]+1);
}
height[v]=d;
count[height[v]]++;
enqueue(v);
}
void gap(int k)
{
for(int v=0;v<n;v++)
{
if(height[v]<k)
continue;
count[height[v]]--;
height[v]=max(height[v], n+1);
count[height[v]]++;
enqueue(v);
}
}
void discharge(int v)
{
for(int i=0; excess[v]>0 && i<g[v].size(); i++)
push(g[v][i]);
if(excess[v]>0)
{
if(count[height[v]]==1)
gap(height[v]);
else
relabel(v);
}
}
long long max_flow(int source, int dest)
{
count[0] = n-1;
count[n] = 1;
height[source] = n;
active[source] = active[dest] = 1;
for(auto &it:g[source])
{
excess[source]+=it.cap;
push(it);
}
while(!Q.empty())
{
int v=Q.front();
Q.pop();
active[v]=false;
discharge(v);
}
long long max_flow=0;
for(auto &e:g[source])
max_flow+=e.flow;
return max_flow;
}
};
int n, m;
int conv(int i, int j, int t) {
return i * m + j + t * (n * m);
}
char arr[N][N];
void solve() {
int t;
cin >> n >> m >> t;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> arr[i][j];
}
}
int src = 3 * n * m * (t + 1), sink = src + 1;
PushRelabel flw(sink + 1);
// handle src to nodes
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (arr[i][j] == 'P') {
flw.addEdge(src, 2 * conv(i, j, 0), 1);
}
}
}
// handle nodes to sink
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (arr[i][j] == 'E') {
for (int k = 0; k <= t; ++k) {
flw.addEdge(2 * conv(i, j, k) + 1, sink, 1);
}
}
}
}
// handle nodes to nodes
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (arr[i][j] == '#')continue;
for (int k = 0; k < 4; ++k) {
int ni = i + dx[k];
int nj = j + dy[k];
if (ni < 0 || ni >= n || nj < 0 || nj >= m || arr[ni][nj] == '#')continue;
for (int l = 0; l < t; ++l) {
flw.addEdge(2 * conv(i, j, l) + 1, 2 * conv(ni, nj, l + 1), 1);
}
}
}
}
// handle nodes it itself
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (arr[i][j] == '#')continue;
for (int k = 0; k <= t; ++k) {
flw.addEdge(2 * conv(i, j, k), 2 * conv(i, j, k) + 1, 1);
if (k != t)flw.addEdge(2 * conv(i, j, k) + 1, 2 * conv(i, j, k + 1), 1);
}
}
}
cout << flw.calc(src, sink);
}
signed main() {
Gamal();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}