[BOJ] 18428. 감시 피하기

import java.util.Scanner;

public class Main {
	static int N;
	static char[][] map;
	static boolean ans = false;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		map = new char[N][N];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				map[i][j] = sc.next().charAt(0);
			}
		}
		
		wall(0);
		
		if(ans) System.out.println("YES");
		else System.out.println("NO");
	}
	
	static void wall(int depth) {
		if(ans) return;
		if(depth == 3) {			
			if(!check()) ans = true;			
			return;
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(map[i][j] == 'X') {
					map[i][j] = 'O';
					wall(depth + 1);
					map[i][j] = 'X';
				}
			}
		}
	}
	
	static boolean check() {	
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(map[i][j] == 'T') {
					if(upCheck(i,j)) return true;
					if(downCheck(i,j)) return true;
					if(leftCheck(i,j)) return true;
					if(rightCheck(i,j)) return true;
				}
			}
		}
		return false;
	}

	static boolean upCheck(int y, int x) {
		for(int i = y; i >= 0; i--) {
			if(map[i][x] == 'O') return false;
			if(map[i][x] == 'S') return true;
		}
		return false;
	}
	
	static boolean downCheck(int y, int x) {
		for(int i = y; i < N; i++) {
			if(map[i][x] == 'O') return false;
			if(map[i][x] == 'S') return true;
		}
		return false;
	}
	
	static boolean leftCheck(int y, int x) {
		for(int i = x; i >= 0; i--) {
			if(map[y][i] == 'O') return false;
			if(map[y][i] == 'S') return true;
		}
		return false;
	}
	
	static boolean rightCheck(int y, int x) {
		for(int i = x; i < N; i++) {
			if(map[y][i] == 'O') return false;
			if(map[y][i] == 'S') return true;
		}
		return false;
	}
}