package ieee;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;

import org.w3c.dom.NodeList;

public class IEEE_D
{
    private static ArrayList<TNode> route_ = new ArrayList<TNode>();
    private static ArrayList<TNode> nodes_ = new ArrayList<TNode>();

    public static int bestRouteCost_ = Integer.MAX_VALUE;
    public static char[][] map_;

    public static void main(String[] args)
    {
        IPoint startPoint = null;
        IPoint endPoint = null;

        ArrayList<IPoint> keyPointList = new ArrayList<IPoint>();
        ArrayList<IPoint> doorPointList = new ArrayList<IPoint>();

        SimpleFileReader reader = new SimpleFileReader("ieee_d" + File.separator + "input2.txt");
        String currentLine = reader.nextLine();

        int rowCount, columnCount;
        String[] line = currentLine.split(" ");
        rowCount = Integer.parseInt(line[0]);
        columnCount = Integer.parseInt(line[1]);

        map_ = new char[columnCount][rowCount];

        int y = 0;
        currentLine = reader.nextLine();
        while(currentLine != null)
        {
            char[] lineChars = currentLine.toCharArray();
            for(int x = 0; x < lineChars.length; ++x)
            {
                map_[x][y] = lineChars[x];
                if(lineChars[x] == 'K')
                    keyPointList.add(new IPoint(x, y));
                else if(lineChars[x] == 'D')
                    doorPointList.add(new IPoint(x, y));
                else if(lineChars[x] == 'S')
                    startPoint = new IPoint(x, y);
                else if(lineChars[x] == 'E')
                    endPoint = new IPoint(x, y);
            }
            currentLine = reader.nextLine();
            ++y;
        }

        //make nodes for each point of interest
        TNode startNode = new TNode(TNode.Type.S, startPoint);
        TNode endNode = new TNode(TNode.Type.E, endPoint);

        nodes_.add(startNode);
        for(IPoint point : keyPointList)
        {
            nodes_.add(new TNode(TNode.Type.K, point));
        }
        for(IPoint point : doorPointList)
        {
            nodes_.add(new TNode(TNode.Type.D, point));
        }
        nodes_.add(endNode);

        //Depth first that shit. Lowest is bestest
        depthFirst(startNode, 0, 0);
        System.out.print(bestRouteCost_);
    }

    public static void depthFirst(TNode startNode, int keys, int cost)
    {
        route_.add(startNode);

        startNode.connectedNodes_.clear();
        for(TNode jNode : nodes_)
        {
            if(startNode.equals(jNode) || startNode.isConnected(jNode)) continue;
            Route route = Astar(startNode.position_, jNode.position_);
            if(route == null) continue; //no connection exists
            else
            {
                startNode.connect(jNode, route.path_.size() - 1);
            }
        }

        int currentKeyCount = keys;
        int routeLength = cost;

        TNode currentNode = startNode;
        if(currentNode.type_ == TNode.Type.E)
        {
            //found the end point, check route cost
            if(routeLength < bestRouteCost_) bestRouteCost_ = routeLength;
            route_.remove(route_.indexOf(startNode));
            return;
        }
        //check if this node has a key, to add to our count
        else if(currentNode.type_ == TNode.Type.K) ++currentKeyCount;
        //or is a door, to use up keys
        else if(currentNode.type_ == TNode.Type.D)
        {
            //switch to an open door
            currentNode.type_ = TNode.Type.O;
            map_[currentNode.position_.x_][currentNode.position_.y_] = 'O';
            --currentKeyCount;
        }

        for(int i = 0; i < currentNode.connectedNodes_.size(); ++i)
        {
            TNode nextNode = currentNode.connectedNodes_.get(i);
            int weight = currentNode.weights_.get(i);

            //check if the next node is visited already
            if(route_.contains(nextNode)) continue;
            //check if the next node is a door, to make sure we have enough keys
            if(nextNode.type_ == TNode.Type.D && currentKeyCount == 0) continue;

            depthFirst(nextNode, currentKeyCount, cost + weight);
        }

        //we can't do tail recursion here since we need to reset the state of door nodes after we finish with them
        if(currentNode.type_ == TNode.Type.O)
        {
            //switch to a closed door
            currentNode.type_ = TNode.Type.D;
            map_[currentNode.position_.x_][currentNode.position_.y_] = 'D';
        }

        route_.remove(route_.indexOf(startNode));
    }

    public static char getTile(IPoint point)
    {
        if(point.x_ >= map_.length || point.y_ >= map_.length) return '#';
        return map_[point.x_][point.y_];
    }

    public static char getTile(int x, int y)
    {
        if(x >= map_.length || y >= map_.length) return 'x';
        return map_[x][y];
    }

    private static Route Astar(IPoint start, IPoint end)
    {
        int doorBetweenCount = 0;
        ANode startNode = new ANode(start, null);
        ArrayList<ANode> closedSet = new ArrayList<ANode>();
        ArrayList<ANode> openSet = new ArrayList<ANode>();
        openSet.add(startNode);

        startNode.g_ = 0;
        startNode.h_ = getDistance(start, end);
        startNode.f_ = startNode.g_ + startNode.h_;

        while(!openSet.isEmpty())
        {
            //pick smallest f from openSet
            int maxF = Integer.MAX_VALUE;
            ANode currentNode = null;
            for(ANode node : openSet)
            {
                if(node.f_ < maxF)
                {
                    maxF = node.f_;
                    currentNode = node;
                }
            }
            if(currentNode.point_.equals(end))
            {
                return buildRoute(currentNode, doorBetweenCount);
            }
            //remove node from openSet and add to closed
            openSet.remove(currentNode);
            closedSet.add(currentNode);

            //get adjacent squares, ignore doors unless it is the end point
            IPoint lookingPoint;
            ANode newNode;
            char lookingChar;

            for(int i = 0; i < 4; ++i)
            {
                //check left, right, up and down
                int xOffset = 0, yOffset = 0;
                if(i == 0) xOffset = -1;
                else if(i == 1) xOffset = +1;
                else if(i == 2) yOffset = -1;
                else if(i == 3) yOffset = +1;

                lookingChar = getTile(currentNode.point_.x_ + xOffset, currentNode.point_.y_ + yOffset);
                if(lookingChar != '#') //add to openSet
                {
                    lookingPoint = new IPoint(currentNode.point_.x_ + xOffset, currentNode.point_.y_ + yOffset);
                    //shitty hack, check if it's a door
                    if(lookingChar == 'D' && !lookingPoint.equals(end)) continue;

                    newNode = new ANode(lookingPoint, currentNode);
                    if(closedSet.contains(newNode)) continue;

                    //yeah this is sloppy but I don't care
                    newNode.g_ = currentNode.g_ + 1;
                    newNode.h_ = getDistance(lookingPoint, end);
                    newNode.f_ = newNode.g_ + newNode.h_;
                    if(!openSet.contains(newNode))
                        openSet.add(newNode);
                    else
                    {
                        ANode existing = openSet.get(openSet.indexOf(newNode));
                        if(existing.g_ < newNode.g_)
                        {
                            existing.g_ = newNode.g_;
                            existing.f_ = existing.g_ + existing.h_;
                            existing.parent_ = currentNode;
                        }
                    }

                }
            }
        }
        return null;
    }

    private static Route buildRoute(ANode currentNode, int doorBetweenCount)
    {
        Route newRoute = new Route(currentNode.point_, doorBetweenCount);
        ANode parent = currentNode.parent_;
        while(parent != null)
        {
            newRoute.add(parent.point_);
            parent = parent.parent_;
        }
        return newRoute;
    }

    private static int getDistance(IPoint start, IPoint end)
    {
        return Math.abs((end.x_ - start.x_)) + Math.abs((end.y_ - start.y_));
    }
}

class ANode
{
    public ANode parent_;
    public int g_ = 0;
    public int h_ = 0;
    public int f_ = 0;
    public IPoint point_;

    public ANode(IPoint point, ANode parent)
    {
        point_ = point;
        parent_ = parent;
    }

    @Override
    public boolean equals(Object obj)
    {
        if(obj instanceof ANode)
        {
            return point_.equals(((ANode) obj).point_);
        }
        return false;
    }

    @Override
    public String toString()
    {
        return point_.toString();
    }
}

class TNode
{
    public static enum Type {S, K, D, E, O};
    public IPoint position_;
    public Type type_;
    ArrayList<TNode> connectedNodes_;
    ArrayList<Integer> weights_;

    public TNode(Type type, IPoint position)
    {
        type_ = type;
        position_ = position;
        connectedNodes_ = new ArrayList<TNode>();
        weights_ = new ArrayList<Integer>();
    }

    public boolean isConnected(TNode node)
    {
        return connectedNodes_.contains(node);
    }

    public void connect(TNode node, int weight)
    {
        connectedNodes_.add(node);
        weights_.add(weight);
    }

    @Override
    public boolean equals(Object obj)
    {
        if(obj instanceof TNode)
        {
            return position_.equals(((TNode) obj).position_);
        }
        return false;
    }

    @Override
    public String toString()
    {
        return type_.toString() + ":" + position_.toString();
    }

    @Override
    public int hashCode()
    {
        return position_.hashCode();
    }
}

class Route
{
    public ArrayList<IPoint> path_;
    public int doorCount_ = 0;

    public Route(IPoint startPos, int doorCount)
    {
        doorCount_ = doorCount;
        path_ = new ArrayList<IPoint>();
        path_.add(startPos);
    }

    public void add(IPoint point)
    {
        path_.add(point);
    }

    @Override
    public String toString()
    {
        return path_.toString();
    }
}

class IPoint
{
    public int x_, y_;

    public IPoint(int x, int y)
    {
        x_ = x;
        y_ = y;
    }

    public IPoint()
    {
        x_ = 0;
        y_ = 0;
    }

    @Override
    public String toString()
    {
        return (x_ + "," + y_);
    }

    @Override
    public boolean equals(Object p)
    {
        if(p instanceof IPoint)
        {
            if(((IPoint) p).x_ == x_ && ((IPoint) p).y_ == y_)
                return true;
        }
        return false;
    }

    @Override
    public int hashCode()
    {
        return toString().hashCode();
    }
}

class SimpleFileReader
{
    private File file_;
    private BufferedReader reader_;

    public SimpleFileReader(String fileName)
    {
        file_ = new File(fileName);
        try
        {
            reader_ = new BufferedReader(new FileReader(file_));
        }
        catch (FileNotFoundException e)
        {
            e.printStackTrace();
        }
    }

    public String nextLine()
    {
        String line = null;
        try
        {
            line = reader_.readLine();

            if(line == null)
                reader_.close();

            return line;
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }

        return line;
    }
}