Guest User

Untitled

a guest
Jun 24th, 2018
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.19 KB | None | 0 0
  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. }
Add Comment
Please, Sign In to add comment