Desert Queen

import java.util.*;

public class Main {
    private static final int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    private static boolean isValidMove(int x, int y, int gridSize, char[][] grid) {
        return x >= 0 && x < gridSize && y >= 0 && y < gridSize && grid[x][y] != 'M';
    }

    private static int findMinCost(int gridSize, char[][] grid, int[] startPos, int[] endPos) {
        int[][] minCost = new int[gridSize][gridSize];
        for (int i = 0; i < gridSize; i++) {
            Arrays.fill(minCost[i], Integer.MAX_VALUE);
        }

        Queue<int[]> bfsQueue = new LinkedList<>();
        bfsQueue.add(startPos);
        minCost[startPos[0]][startPos[1]] = 0;

        while (!bfsQueue.isEmpty()) {
            int[] currentPos = bfsQueue.poll();
            int x = currentPos[0];
            int y = currentPos[1];

            for (int[] direction : directions) {
                int nextX = x + direction[0];
                int nextY = y + direction[1];

                if (isValidMove(nextX, nextY, gridSize, grid)) {
                    int moveCost = (grid[x][y] == 'T' && grid[nextX][nextY] == 'T') ? 0 : 1;
                    if (minCost[x][y] + moveCost < minCost[nextX][nextY]) {
                        minCost[nextX][nextY] = minCost[x][y] + moveCost;
                        bfsQueue.add(new int[]{nextX, nextY});
                    }
                }
            }
        }

        return minCost[endPos[0]][endPos[1]];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int gridSize = sc.nextInt();
        char[][] grid = new char[gridSize][gridSize];
        int[] startPos = new int[2];
        int[] endPos = new int[2];

        for (int i = 0; i < gridSize; i++) {
            for (int j = 0; j < gridSize; j++) {
                grid[i][j] = sc.next().charAt(0);
                if (grid[i][j] == 'S') startPos = new int[]{i, j};
                if (grid[i][j] == 'E') endPos = new int[]{i, j};
            }
        }

        int result = findMinCost(gridSize, grid, startPos, endPos);
        System.out.println(result);
    }
}