Advertisement
Guest User

Untitled

a guest
Feb 21st, 2019
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.94 KB | None | 0 0
  1. import java.util.*;
  2. /**
  3. *
  4. * @author Alexander
  5. */
  6. public class Maze {
  7.  
  8. /**
  9. * @param args the command line arguments
  10. */
  11. public static void main(String[] args){
  12. Scanner input = new Scanner(System.in);
  13. int tcase = input.nextInt();
  14. for (int i = 0;i<tcase;i++){
  15. int rows = input.nextInt();
  16. int columns = input.nextInt();
  17. char [][] maze = new char[rows][columns];
  18. input.nextLine();
  19. for (int r = 0;r<rows;r++){
  20. String temp = input.nextLine();
  21. for (int c = 0;c<columns;c++){
  22. maze[r][c] = temp.charAt(c);
  23. }
  24. }
  25. Queue <Integer> row = new LinkedList();
  26. Queue <Integer> column = new LinkedList();
  27. int [][] px = new int [rows][columns];
  28. int [][] py = new int [rows][columns];
  29. boolean [][] visited = new boolean[rows][columns];
  30. visited[0][0] = true;
  31. row.add(0);
  32. column.add(0);
  33. int count = 1;
  34. while (!row.isEmpty()){
  35. int r = row.poll();
  36. int c = column.poll();
  37. if (maze[r][c]=='+'){
  38. if (r>0&&maze[r-1][c]!='*'&&!visited[r-1][c]){
  39. visited[r-1][c] = true;
  40. py[r-1][c] = r;
  41. px[r-1][c] = c;
  42. row.add(r-1);
  43. column.add(c);
  44. }
  45. if (r<rows-1&&maze[r+1][c]!='*'&&!visited[r+1][c]){
  46. visited[r+1][c] = true;
  47. py[r+1][c] = r;
  48. px[r+1][c] = c;
  49. row.add(r+1);
  50. column.add(c);
  51. }
  52. if (c>0&&maze[r][c-1]!='*'&&!visited[r][c-1]){
  53. visited[r][c-1] = true;
  54. py[r][c-1] = r;
  55. px[r][c-1] = c;
  56. row.add(r);
  57. column.add(c-1);
  58. }
  59. if (c<columns-1&&maze[r][c+1]!='*'&&!visited[r][c+1]){
  60. visited[r][c+1] = true;
  61. py[r][c+1] = r;
  62. px[r][c+1] = c;
  63. row.add(r);
  64. column.add(c+1);
  65. }
  66. }
  67. else if(maze[r][c]=='-'){
  68. if (c>0&&maze[r][c-1]!='*'&&!visited[r][c-1]){
  69. visited[r][c-1] = true;
  70. py[r][c-1] = r;
  71. px[r][c-1] = c;
  72. row.add(r);
  73. column.add(c-1);
  74. }
  75. if (c<columns-1&&maze[r][c+1]!='*'&&!visited[r][c+1]){
  76. visited[r][c+1] = true;
  77. py[r][c+1] = r;
  78. px[r][c+1] = c;
  79. row.add(r);
  80. column.add(c+1);
  81. }
  82. }
  83. else if(maze[r][c]=='|'){
  84. if (r>0&&maze[r-1][c]!='*'&&!visited[r-1][c]){
  85. visited[r-1][c] = true;
  86. py[r-1][c] = r;
  87. px[r-1][c] = c;
  88. row.add(r-1);
  89. column.add(c);
  90. }
  91. if (r<rows-1&&maze[r+1][c]!='*'&&!visited[r+1][c]){
  92. visited[r+1][c] = true;
  93. py[r+1][c] = r;
  94. px[r+1][c] = c;
  95. row.add(r+1);
  96. column.add(c);
  97. }
  98. }
  99. }
  100. /*for (int r = 0;r<rows;r++){
  101. for (int c = 0;c<columns;c++){
  102. if (c==columns-1){
  103. System.out.println(px[r][c]);
  104. }
  105. else {
  106. System.out.print(px[r][c] + " ");
  107. }
  108. }
  109. }for (int r = 0;r<rows;r++){
  110. for (int c = 0;c<columns;c++){
  111. if (c==columns-1){
  112. System.out.println(py[r][c]);
  113. }
  114. else {
  115. System.out.print(py[r][c] + " ");
  116. }
  117. }
  118. }*/
  119. if (visited[rows-1][columns-1]){
  120. int y = rows-1;
  121. int x = columns-1;
  122. while(!(y==0&&x==0)){
  123. int tempx = x;
  124. int tempy = y;
  125. x = px[tempy][tempx];
  126. y = py[tempy][tempx];
  127. count++;
  128. }
  129. System.out.println(count);
  130. }
  131. else {
  132. System.out.println("-1");
  133. }
  134. }
  135. }
  136. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement