daily pastebin goal
59%
SHARE
TWEET

Untitled

a guest Jun 24th, 2018 56 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. import java.util.LinkedList;
  2. import java.util.Queue;
  3. import java.util.Scanner;
  4. public class UVA_10047 {
  5.     static int n, m;
  6.     public static void main(String[] args) {
  7.         Scanner sc = new Scanner(System.in);
  8.         while (sc.hasNext()) {
  9.             n = sc.nextInt();
  10.             m = sc.nextInt();
  11.             if (n == 0 && m == 0)
  12.                 break;
  13.             char[][] map = new char[n][m];
  14.             boolean[][][][] v = new boolean[4][5][n][m];
  15.             for (int i = 0; i < n; i++)
  16.                 map[i] = sc.next().toCharArray();
  17.             int sx = 0, sy = 0, ex = 0, ey = 0;
  18.  
  19.             for (int i = 0; i < n; i++)
  20.                 for (int j = 0; j < m; j++)
  21.                     if (map[i][j] == 'S') {
  22.                         sx = i;
  23.                         sy = j;
  24.                     } else if (map[i][j] == 'T') {
  25.                         ex = i;
  26.                         ey = j;
  27.                     }
  28.             int t = bfs(map, v, sx, sy, ex, ey);
  29.             System.out.println(t);
  30.         }
  31.     }
  32.     static int[] dx = { -1, 0, 1, 0 };
  33.     static int[] dy = { 0, 1, 0, -1 };
  34.  
  35.     private static int bfs(char[][] map2, boolean[][][][] v, int sx, int sy,
  36.             int ex, int ey) {
  37.  
  38.         Queue<enternal> q = new LinkedList<enternal>();
  39.         q.add(new enternal(sx, sy, 0, 0, 0));
  40.  
  41.         while (!q.isEmpty()) {
  42.             enternal ob = q.poll();
  43.             int x = ob.x;
  44.             int y = ob.y;
  45.             int t = ob.t;
  46.             int dir = ob.dir;
  47.             int color = ob.color;
  48.             if (x == ex && y == ey && color == 0)
  49.                 return t;
  50.  
  51.             int newX = x + dx[dir];
  52.             int newY = y + dy[dir];
  53.  
  54.             if (okay(map2, v, newX, newY, color, dir)) {
  55.                 q.add(new enternal(newX, newY, t + 1, color + 1, dir));
  56.                 v[dir][color][newX][newY] = true;
  57.             }
  58.             int newDir = (dir + 1) % 4;
  59.             if (!v[newDir][color][x][y]) {
  60.                 q.add(new enternal(x, y, t + 1, color, newDir));
  61.                 v[newDir][color][x][y] = true;
  62.             }
  63.             newDir = dir == 0 ? 3 : dir - 1;
  64.             if (!v[newDir][color][x][y]) {
  65.                 q.add(new enternal(x, y, t + 1, color, newDir));
  66.                 v[newDir][color][x][y] = true;
  67.             }
  68.         }
  69.         return -1;
  70.     }
  71.  
  72.     static boolean okay(char[][] map, boolean[][][][] v, int x, int y,
  73.             int color, int dir) {
  74.         return x >= 0 && y >= 0 && x < n && y < m && map[x][y] != '#'
  75.                 && !v[dir][color][x][y];
  76.     }
  77. }
  78. class enternal {
  79.     int x, y, t, color, dir;
  80.     public enternal(int x, int y, int t, int color, int dir) {
  81.         this.x = x;
  82.         this.y = y;
  83.         this.t = t;
  84.         this.color = color % 5;
  85.         this.dir = dir;
  86.     }
  87. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top