#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

struct solve {
   int x, y, d;
   solve(int x_, int y_, int d_)
   : x(x_), y(y_), d(d_)
   {
   }
};

int main( )
{
   std::ios_base::sync_with_stdio(false);
   std::cin.tie(nullptr);
   std::cout.tie(nullptr);
   //freopen("in.txt", "r", stdin);

   int n, m, k;
   std::cin >> n >> m >> k;

   bool memo[n][m];
   std::fill(&memo[0][0], &memo[n][0], false);
   char mapa[n][m];
   std::vector<std::pair<int, int>> especiales;
   std::pair<int, int> mario, peach;

   for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
         std::cin >> mapa[i][j];
         if (mapa[i][j] == 'M') {
            mario = { i, j };
         } else if (mapa[i][j] == 'P') {
            peach = { i, j };
         } else if (mapa[i][j] == 'E') {
            especiales.push_back({ i, j });
         }
      }
   }

   /*BFS*/
   int res = 0, pasos = 0;
   std::queue<solve> cola;
   cola.push(solve( mario.first, mario.second, 0 ));

   while (!cola.empty( )) {
      ++pasos;
      solve actual = cola.front( );
      cola.pop( );

      if (actual.x == peach.first && actual.y == peach.second) {
         res = actual.d;
         break;
      }
      if (memo[actual.x][actual.y]) {
         continue;
      }
      memo[actual.x][actual.y] = true;

      if (pasos == k) {
         for (auto vecino : especiales) {
            if (!memo[vecino.first][vecino.second]) {
               cola.push(solve( vecino.first, vecino.second, k ));
            } else if () {

            }
         }
      }

      for (auto vecino : std::initializer_list<std::pair<int, int>>{ { actual.x + 1, actual.y }, { actual.x - 1, actual.y }, { actual.x, actual.y + 1 }, { actual.x, actual.y - 1 } }) {
         if (vecino.first >= 0 && vecino.first < n && vecino.second >= 0 && vecino.second < m && !memo[vecino.first][vecino.second]) {
            if (mapa[vecino.first][vecino.second] != '#') {
               cola.push(solve( vecino.first, vecino.second, actual.d + 1 ));
            } else {
               cola.push(solve( vecino.first, vecino.second, actual.d + 2 ));
            }
         }
      }
   }
   /*Fin BFS*/


   std::cout << res << "\n";
}