Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- public class B {
- public static int[] dxx = {-1, 1, 0, 0};
- public static int[] dyy = {0, 0, -1, 1};
- public static void solve() {
- Kattio in = new Kattio(System.in);
- int n = in.nextInt();
- int m = in.nextInt();
- char[][] grid = new char[n][m];
- boolean[][] vis = new boolean[n][m];
- int sx = 0;
- int sy = 0;
- for(int i= 0; i < n; i++) {
- char[] line = in.next().toCharArray();
- for(int j = 0; j < m; j++) {
- grid[i][j] = line[j];
- if(grid[i][j] == 'S') {
- sx = i;
- sy = j;
- }
- }
- }
- ArrayDeque<Triple> q = new ArrayDeque<Triple>();
- q.offer(new Triple(sx, sy, 'n', 0));
- boolean ans = false;
- while(!q.isEmpty()) {
- Triple state = q.poll();
- int x = state.f;
- int y = state.s;
- if(grid[x][y] == 'T') {
- ans = true;
- break;
- }
- if(vis[x][y]) continue;
- vis[x][y] = true;
- char dir = state.dir;
- int turns = state.turns;
- //System.err.println(x+" "+y+" "+dir+" "+turns);
- for(int i = 0; i < dxx.length; i++) {
- int xx = x + dxx[i];
- int yy = y + dyy[i];
- if(xx < 0 || xx >= n) continue;
- if(yy < 0 || yy >= m) continue;
- if(grid[xx][yy] == '*') continue;
- int dx = dxx[i];
- int dy = dyy[i];
- //if(vis[xx][yy]) continue;
- if(dx > 0) {
- if(dir != 'n' && dir == 'b') {
- q.offer(new Triple(xx, yy, 'b', turns));
- }else if(dir != 'n' && dir != 'b') {
- if(turns < 2) {
- q.offer(new Triple(xx, yy, 'b', turns+1));
- }
- }else if(dir == 'n') {
- q.offer(new Triple(xx, yy, 'b', 0));
- }
- } else if(dx < 0) {
- if(dir != 'n' && dir == 't') {
- q.offer(new Triple(xx, yy, 't', turns));
- }else if(dir != 'n' && dir != 't') {
- if(turns < 2) {
- q.offer(new Triple(xx, yy, 't', turns+1));
- }
- }else if(dir == 'n') {
- q.offer(new Triple(xx, yy, 't', 0));
- }
- } else if(dy > 0){
- if(dir != 'n' && dir == 'r') {
- q.offer(new Triple(xx, yy, 'r', turns));
- }else if(dir != 'n' && dir != 'r') {
- if(turns < 2) {
- q.offer(new Triple(xx, yy, 'r', turns+1));
- }
- }else if(dir == 'n') {
- q.offer(new Triple(xx, yy, 'r', 0));
- }
- } else if(dy < 0) {
- if(dir != 'n' && dir == 'l') {
- q.offer(new Triple(xx, yy, 'l', 0));
- }else if(dir != 'n' && dir != 'l') {
- if(turns < 2) {
- q.offer(new Triple(xx, yy, 'l', turns+1));
- }
- }else if(dir == 'n') {
- q.offer(new Triple(xx, yy, 'l', 0));
- }
- }
- }
- }
- if(ans) in.println("YES");
- else in.println("NO");
- in.flush();
- in.close();
- }
- public static void main(String args[] ) throws Exception {
- Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){
- @Override
- public void run() {
- solve();
- }
- };
- t.start();
- t.join();
- }
- private static class Kattio extends PrintWriter {
- private BufferedReader r;
- private String line;
- private StringTokenizer st;
- private String token;
- public Kattio(InputStream i) {
- super(new BufferedOutputStream(System.out));
- r = new BufferedReader(new InputStreamReader(i));
- }
- public Kattio(InputStream i, OutputStream o) {
- super(new BufferedOutputStream(o));
- r = new BufferedReader(new InputStreamReader(i));
- }
- public boolean hasNext() {
- return peekToken() != null;
- }
- public int nextInt() {
- return Integer.parseInt(nextToken());
- }
- public double nextDouble() {
- return Double.parseDouble(nextToken());
- }
- public long nextLong() {
- return Long.parseLong(nextToken());
- }
- public String next() {
- return nextToken();
- }
- public String nextLine() {
- token = null;
- st = null;
- try {
- return r.readLine();
- } catch (IOException e) {
- return null;
- }
- }
- private String peekToken() {
- if (token == null)
- try {
- while (st == null || !st.hasMoreTokens()) {
- line = r.readLine();
- if (line == null) return null;
- st = new StringTokenizer(line);
- }
- token = st.nextToken();
- } catch (IOException e) { }
- return token;
- }
- private String nextToken() {
- String ans = peekToken();
- token = null;
- return ans;
- }
- }
- }
- class Triple {
- int f, s;
- char dir;
- int turns;
- public Triple(int f, int s, char dir, int turns) {
- this.f = f;
- this.s = s;
- this.dir = dir;
- this.turns = turns;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement