Guest User

Untitled

a guest
Apr 23rd, 2017
207
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.StringTokenizer;
  5.  
  6. public class TinkoffA {
  7.  
  8. public enum Direction {
  9. UP, RIGHT, DOWN, LEFT, START;
  10. }
  11.  
  12. public static void solve(char[][] maze, int x, int y, int turns, Direction dir) {
  13. if ((x < 0) || (y < 0) || (x >= maze.length) || (y >= maze[0].length)) {
  14. return;
  15. }
  16.  
  17. // System.out.println(x);
  18. // System.out.println(y);
  19.  
  20. if (turns > 3) {
  21. return;
  22. }
  23.  
  24. if (maze[x][y] == 'T') {
  25. found = true;
  26. return;
  27. }
  28.  
  29. if (!(maze[x][y] == '.')) {
  30. return;
  31. }
  32.  
  33. maze[x][y] = 's';
  34.  
  35. if (dir != Direction.DOWN) {
  36. solve(maze, x - 1, y, turns + 1, Direction.DOWN);
  37. } else {
  38. solve(maze, x - 1, y, turns, Direction.DOWN);
  39. }
  40.  
  41. if (dir != Direction.UP) {
  42. solve(maze, x + 1, y, turns + 1, Direction.UP);
  43. } else {
  44. solve(maze, x + 1, y, turns, Direction.UP);
  45. }
  46.  
  47. if (dir != Direction.LEFT) {
  48. solve(maze, x, y - 1, turns + 1, Direction.LEFT);
  49. } else {
  50. solve(maze, x, y - 1, turns, Direction.LEFT);
  51. }
  52.  
  53. if (dir != Direction.RIGHT) {
  54. solve(maze, x, y + 1, turns + 1, Direction.RIGHT);
  55. } else {
  56. solve(maze, x, y + 1, turns, Direction.RIGHT);
  57. }
  58.  
  59. maze[x][y] = '.'; // BACKTRACK
  60. }
  61.  
  62. static boolean found = false;
  63.  
  64. public static void main(String[] args) {
  65.  
  66. MyScanner reader = new MyScanner();
  67.  
  68. int n = reader.nextInt();
  69. int m = reader.nextInt();
  70. int startX = 0, startY = 0;
  71. char[][] grid = new char[n][m];
  72. for (int i = 0; i < n; i++) {
  73. String line = reader.next();
  74. for (int j = 0; j < m; j++) {
  75. grid[i][j] = (line.charAt(j));
  76. if (grid[i][j] == 'S') {
  77. startX = i;
  78. startY = j;
  79. grid[i][j] = '.';
  80. }
  81. }
  82. }
  83. solve(grid, startX, startY, 0, Direction.START);
  84. if (found) {
  85. System.out.println("YES");
  86. } else {
  87. System.out.println("NO");
  88. }
  89. }
  90.  
  91. public static class MyScanner {
  92. BufferedReader br;
  93. StringTokenizer st;
  94.  
  95. public MyScanner() {
  96. br = new BufferedReader(new InputStreamReader(System.in));
  97. }
  98.  
  99. String next() {
  100. while (st == null || !st.hasMoreElements()) {
  101. try {
  102. st = new StringTokenizer(br.readLine());
  103. } catch (IOException e) {
  104. e.printStackTrace();
  105. }
  106. }
  107. return st.nextToken();
  108. }
  109.  
  110. int nextInt() {
  111. return Integer.parseInt(next());
  112. }
  113. }
  114.  
  115. }
RAW Paste Data