#include <iostream>
#include <vector>
#include <queue>
#include <array>

struct State
{
	int x, y;
	bool hasKey;
	int dist;
};

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int N, M;
	std::cin >> N >> M;
	std::vector<std::string> grid(N);
	for (int i = 0; i < N; i++)
		std::cin >> grid[i];

	// Directions: up, down, left, right
	int dx[4] = {-1, 1, 0, 0};
	int dy[4] = {0, 0, -1, 1};

	std::pair<int, int> start, exit;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (grid[i][j] == 'S')
				start = {i, j};
			if (grid[i][j] == 'E')
				exit = {i, j};
		}
	}

	// visited[x][y][key_state] : 0=no key, 1=has key
	std::vector<std::vector<std::array<bool, 2>>> visited(N, std::vector<std::array<bool, 2>>(M, {false, false}));

	std::queue<State> q;
	q.push({start.first, start.second, false, 0});
	visited[start.first][start.second][0] = true;

	while (!q.empty())
	{
		auto cur = q.front();
		q.pop();
		int x = cur.x, y = cur.y;
		bool hasKey = cur.hasKey;
		int dist = cur.dist;

		if (x == exit.first && y == exit.second)
		{
			std::cout << dist << "\n";
			return 0;
		}

		for (int dir = 0; dir < 4; dir++)
		{
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			bool nextKey = hasKey;

			if (nx < 0 || ny < 0 || nx >= N || ny >= M)
				continue;
			char cell = grid[nx][ny];

			if (cell == '#')
				continue; // wall
			if (cell == 'D' && !hasKey)
				continue; // locked door, no key yet
			if (cell == 'K')
				nextKey = true; // pick up key

			int keyState = nextKey ? 1 : 0;
			if (!visited[nx][ny][keyState])
			{
				visited[nx][ny][keyState] = true;
				q.push({nx, ny, nextKey, dist + 1});
			}
		}
	}

	std::cout << -1 << "\n"; // no path
	return 0;
}
