Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2017
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 6.15 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4.  
  5. public class B {
  6.    
  7.     public static int[] dxx = {-1, 1, 0, 0};
  8.     public static int[] dyy = {0, 0, -1, 1};
  9.     public static void solve() {
  10.         Kattio in = new Kattio(System.in);
  11.        
  12.         int n = in.nextInt();
  13.         int m = in.nextInt();
  14.         char[][] grid = new char[n][m];
  15.         boolean[][] vis = new boolean[n][m];
  16.         int sx = 0;
  17.         int sy = 0;
  18.         for(int i= 0; i < n; i++) {
  19.             char[] line = in.next().toCharArray();
  20.  
  21.             for(int j = 0; j < m; j++) {
  22.                 grid[i][j] = line[j];
  23.  
  24.                 if(grid[i][j] == 'S') {
  25.                     sx = i;
  26.                     sy = j;
  27.                 }
  28.             }
  29.         }
  30.  
  31.  
  32.         ArrayDeque<Triple> q = new ArrayDeque<Triple>();
  33.         q.offer(new Triple(sx, sy, 'n', 0));
  34.  
  35.  
  36.         boolean ans = false;
  37.         while(!q.isEmpty()) {
  38.             Triple state = q.poll();
  39.             int x = state.f;
  40.             int y = state.s;
  41.  
  42.             if(grid[x][y] == 'T') {
  43.                 ans = true;
  44.                 break;
  45.             }
  46.  
  47.             if(vis[x][y]) continue;
  48.             vis[x][y] = true;
  49.  
  50.  
  51.             char dir = state.dir;
  52.             int turns = state.turns;
  53.  
  54.             //System.err.println(x+" "+y+" "+dir+" "+turns);
  55.  
  56.             for(int i = 0; i < dxx.length; i++) {
  57.                 int xx = x + dxx[i];
  58.                 int yy = y + dyy[i];
  59.  
  60.  
  61.                 if(xx < 0 || xx >= n) continue;
  62.                 if(yy < 0 || yy >= m) continue;
  63.  
  64.                 if(grid[xx][yy] == '*') continue;
  65.  
  66.                 int dx = dxx[i];
  67.                 int dy = dyy[i];
  68.  
  69.                 //if(vis[xx][yy]) continue;
  70.  
  71.  
  72.                 if(dx > 0) {
  73.                     if(dir != 'n' && dir == 'b') {
  74.                         q.offer(new Triple(xx, yy, 'b', turns));
  75.                     }else if(dir != 'n' && dir != 'b') {
  76.                         if(turns < 2) {
  77.                             q.offer(new Triple(xx, yy, 'b', turns+1));
  78.                         }
  79.                     }else if(dir == 'n') {
  80.                         q.offer(new Triple(xx, yy, 'b', 0));
  81.                     }
  82.                 } else if(dx < 0) {
  83.                     if(dir != 'n' && dir == 't') {
  84.                         q.offer(new Triple(xx, yy, 't', turns));
  85.                     }else if(dir != 'n' && dir != 't') {
  86.                         if(turns < 2) {
  87.                             q.offer(new Triple(xx, yy, 't', turns+1));
  88.                         }
  89.                     }else if(dir == 'n') {
  90.                         q.offer(new Triple(xx, yy, 't', 0));
  91.                     }
  92.                 } else if(dy > 0){
  93.                     if(dir != 'n' && dir == 'r') {
  94.                         q.offer(new Triple(xx, yy, 'r', turns));
  95.                     }else if(dir != 'n' && dir != 'r') {
  96.                         if(turns < 2) {
  97.                             q.offer(new Triple(xx, yy, 'r', turns+1));
  98.                         }
  99.                     }else if(dir == 'n') {
  100.                         q.offer(new Triple(xx, yy, 'r', 0));
  101.                     }
  102.                 } else if(dy < 0) {
  103.                     if(dir != 'n' && dir == 'l') {
  104.                         q.offer(new Triple(xx, yy, 'l', 0));
  105.                     }else if(dir != 'n' && dir != 'l') {
  106.                         if(turns < 2) {
  107.                             q.offer(new Triple(xx, yy, 'l', turns+1));
  108.                         }
  109.                     }else if(dir == 'n') {
  110.                         q.offer(new Triple(xx, yy, 'l', 0));
  111.                     }
  112.                 }
  113.  
  114.  
  115.             }
  116.  
  117.         }
  118.  
  119.         if(ans) in.println("YES");
  120.         else in.println("NO");
  121.  
  122.        
  123.  
  124.         in.flush();
  125.         in.close();
  126.     }  
  127.  
  128.     public static void main(String args[] ) throws Exception {
  129.  
  130.  
  131.         Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){
  132.             @Override
  133.             public void run() {
  134.                 solve();
  135.             }
  136.         };
  137.  
  138.         t.start();
  139.         t.join();
  140.  
  141.     }
  142.  
  143.  
  144.  
  145.  
  146.     private static class Kattio extends PrintWriter {
  147.  
  148.         private BufferedReader r;
  149.         private String line;
  150.         private StringTokenizer st;
  151.         private String token;
  152.        
  153.         public Kattio(InputStream i) {
  154.             super(new BufferedOutputStream(System.out));
  155.             r = new BufferedReader(new InputStreamReader(i));
  156.         }
  157.         public Kattio(InputStream i, OutputStream o) {
  158.             super(new BufferedOutputStream(o));
  159.             r = new BufferedReader(new InputStreamReader(i));
  160.         }
  161.  
  162.         public boolean hasNext() {
  163.             return peekToken() != null;
  164.         }
  165.  
  166.         public int nextInt() {
  167.             return Integer.parseInt(nextToken());
  168.         }
  169.  
  170.         public double nextDouble() {
  171.             return Double.parseDouble(nextToken());
  172.         }
  173.  
  174.         public long nextLong() {
  175.             return Long.parseLong(nextToken());
  176.         }
  177.  
  178.         public String next() {
  179.             return nextToken();
  180.         }
  181.        
  182.         public String nextLine() {
  183.             token = null;
  184.             st = null;
  185.             try {
  186.                 return r.readLine();
  187.             } catch (IOException e) {
  188.                 return null;
  189.             }
  190.         }
  191.  
  192.         private String peekToken() {
  193.             if (token == null)
  194.                 try {
  195.                     while (st == null || !st.hasMoreTokens()) {
  196.                         line = r.readLine();
  197.                         if (line == null) return null;
  198.                         st = new StringTokenizer(line);
  199.                     }
  200.                     token = st.nextToken();
  201.                 } catch (IOException e) { }
  202.             return token;
  203.         }
  204.  
  205.         private String nextToken() {
  206.             String ans = peekToken();
  207.             token = null;
  208.             return ans;
  209.         }
  210.     }
  211. }
  212.  
  213.  
  214. class Triple {
  215.     int f, s;
  216.     char dir;
  217.  
  218.     int turns;
  219.     public Triple(int f, int s, char dir, int turns) {
  220.         this.f = f;
  221.         this.s = s;
  222.  
  223.         this.dir = dir;
  224.         this.turns = turns;
  225.     }
  226. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement