class Solution {
  public int getSecondsRequired(int R, int C, char[][] G) {
    // Write your code here
    int startX = 0, startY = 0;
    for (int i = 0; i < R; ++i)
      for (int j = 0; j < C; ++j) {
        if (G[i][j] == 'S') {
          startX = i;
          startY = j;
          break;
        }
      }
    return getMinSeconds(R, C, G, startX, startY);
  }
  
  private int getMinSeconds(int R, int C, char[][] G, int startX, int startY) {
    boolean[][] visited = new boolean[R][C];
    Queue<Move> q = new LinkedList<>();
    q.add(new Move(startX, startY, 0));
    int minX = -1, minY = -1;
    int minSeconds = Integer.MAX_VALUE;
    while(!q.isEmpty()) {
      Move move = q.poll();
      if (G[move.x][move.y] == 'E') {
        if (move.seconds < minSeconds) {
          minSeconds = move.seconds;
          minX = move.x;
          minY = move.y;
        }
        continue;
      }
      visited[move.x][move.y] = true;
      if (move.x > 0) {
        makeMove(q, G, move.x - 1, move.y, move.seconds + 1, visited);
      }
      if (move.y > 0) {
        makeMove(q, G, move.x, move.y - 1, move.seconds + 1, visited);
      }
      if (move.x < R - 1 ) {
        makeMove(q, G, move.x + 1, move.y, move.seconds + 1, visited);
      }
      if (move.y < C - 1) {
        makeMove(q, G, move.x, move.y + 1, move.seconds + 1, visited);
      }
      if (G[move.x][move.y] >= 'a' && G[move.x][move.y] <= 'z') {
        for (int i = 0; i < R; ++i)
          for (int j = 0; j < C; ++j)
            if (G[i][j] == G[move.x][move.y]) {
              makeMove(q, G, i, j, move.seconds + 1, visited);
            }
      }
    }
    return minX != -1 && minY != -1 ? minSeconds : -1;
  }
  
  private void makeMove(Queue q, char[][] G, int x, int y, int secs, boolean[][] visited) {
    if (G[x][y] != '#' && !visited[x][y]) {
      q.add(new Move(x, y, secs));
    }
  }
  
  static class Move {
    int x, y;
    int seconds;
    Move(int x, int y, int seconds) {
      this.x = x;
      this.y = y;
      this.seconds = seconds;
    }
  }
}