Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.StringTokenizer;
- public class TinkoffA {
- public enum Direction {
- UP, RIGHT, DOWN, LEFT, START;
- }
- public static void solve(char[][] maze, int x, int y, int turns, Direction dir) {
- if ((x < 0) || (y < 0) || (x >= maze.length) || (y >= maze[0].length)) {
- return;
- }
- // System.out.println(x);
- // System.out.println(y);
- if (turns > 3) {
- return;
- }
- if (maze[x][y] == 'T') {
- found = true;
- return;
- }
- if (!(maze[x][y] == '.')) {
- return;
- }
- maze[x][y] = 's';
- if (dir != Direction.DOWN) {
- solve(maze, x - 1, y, turns + 1, Direction.DOWN);
- } else {
- solve(maze, x - 1, y, turns, Direction.DOWN);
- }
- if (dir != Direction.UP) {
- solve(maze, x + 1, y, turns + 1, Direction.UP);
- } else {
- solve(maze, x + 1, y, turns, Direction.UP);
- }
- if (dir != Direction.LEFT) {
- solve(maze, x, y - 1, turns + 1, Direction.LEFT);
- } else {
- solve(maze, x, y - 1, turns, Direction.LEFT);
- }
- if (dir != Direction.RIGHT) {
- solve(maze, x, y + 1, turns + 1, Direction.RIGHT);
- } else {
- solve(maze, x, y + 1, turns, Direction.RIGHT);
- }
- maze[x][y] = '.'; // BACKTRACK
- }
- static boolean found = false;
- public static void main(String[] args) {
- MyScanner reader = new MyScanner();
- int n = reader.nextInt();
- int m = reader.nextInt();
- int startX = 0, startY = 0;
- char[][] grid = new char[n][m];
- for (int i = 0; i < n; i++) {
- String line = reader.next();
- for (int j = 0; j < m; j++) {
- grid[i][j] = (line.charAt(j));
- if (grid[i][j] == 'S') {
- startX = i;
- startY = j;
- grid[i][j] = '.';
- }
- }
- }
- solve(grid, startX, startY, 0, Direction.START);
- if (found) {
- System.out.println("YES");
- } else {
- System.out.println("NO");
- }
- }
- public static class MyScanner {
- BufferedReader br;
- StringTokenizer st;
- public MyScanner() {
- br = new BufferedReader(new InputStreamReader(System.in));
- }
- String next() {
- while (st == null || !st.hasMoreElements()) {
- try {
- st = new StringTokenizer(br.readLine());
- } catch (IOException e) {
- e.printStackTrace();
- }
- }
- return st.nextToken();
- }
- int nextInt() {
- return Integer.parseInt(next());
- }
- }
- }
Add Comment
Please, Sign In to add comment