Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.LinkedList;
- import java.util.Queue;
- import java.util.Scanner;
- public class UVA_10047 {
- static int n, m;
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- while (sc.hasNext()) {
- n = sc.nextInt();
- m = sc.nextInt();
- if (n == 0 && m == 0)
- break;
- char[][] map = new char[n][m];
- boolean[][][][] v = new boolean[4][5][n][m];
- for (int i = 0; i < n; i++)
- map[i] = sc.next().toCharArray();
- int sx = 0, sy = 0, ex = 0, ey = 0;
- for (int i = 0; i < n; i++)
- for (int j = 0; j < m; j++)
- if (map[i][j] == 'S') {
- sx = i;
- sy = j;
- } else if (map[i][j] == 'T') {
- ex = i;
- ey = j;
- }
- int t = bfs(map, v, sx, sy, ex, ey);
- System.out.println(t);
- }
- }
- static int[] dx = { -1, 0, 1, 0 };
- static int[] dy = { 0, 1, 0, -1 };
- private static int bfs(char[][] map2, boolean[][][][] v, int sx, int sy,
- int ex, int ey) {
- Queue<enternal> q = new LinkedList<enternal>();
- q.add(new enternal(sx, sy, 0, 0, 0));
- while (!q.isEmpty()) {
- enternal ob = q.poll();
- int x = ob.x;
- int y = ob.y;
- int t = ob.t;
- int dir = ob.dir;
- int color = ob.color;
- if (x == ex && y == ey && color == 0)
- return t;
- int newX = x + dx[dir];
- int newY = y + dy[dir];
- if (okay(map2, v, newX, newY, color, dir)) {
- q.add(new enternal(newX, newY, t + 1, color + 1, dir));
- v[dir][color][newX][newY] = true;
- }
- int newDir = (dir + 1) % 4;
- if (!v[newDir][color][x][y]) {
- q.add(new enternal(x, y, t + 1, color, newDir));
- v[newDir][color][x][y] = true;
- }
- newDir = dir == 0 ? 3 : dir - 1;
- if (!v[newDir][color][x][y]) {
- q.add(new enternal(x, y, t + 1, color, newDir));
- v[newDir][color][x][y] = true;
- }
- }
- return -1;
- }
- static boolean okay(char[][] map, boolean[][][][] v, int x, int y,
- int color, int dir) {
- return x >= 0 && y >= 0 && x < n && y < m && map[x][y] != '#'
- && !v[dir][color][x][y];
- }
- }
- class enternal {
- int x, y, t, color, dir;
- public enternal(int x, int y, int t, int color, int dir) {
- this.x = x;
- this.y = y;
- this.t = t;
- this.color = color % 5;
- this.dir = dir;
- }
- }
Add Comment
Please, Sign In to add comment