Advertisement
Guest User

Untitled

a guest
Nov 14th, 2019
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.39 KB | None | 0 0
  1. import java.util.*;
  2. public class dmopc13p4 {
  3. public static void main(String [] args){
  4. Scanner sc = new Scanner(System.in);
  5. int n = sc.nextInt();
  6. for(int i=0; i<n; i++) {
  7. int l = sc.nextInt();
  8. int w = sc.nextInt();
  9. char [][] room = new char [w][l];
  10.  
  11. int rowStart = 0;
  12. int colStart = 0;
  13. int rowEnd = 0;
  14. int colEnd = 0;
  15.  
  16. for(int width=0; width<w; width++){
  17. room[width] = sc.next().toCharArray();
  18. }
  19.  
  20. int step [][] = new int [w][l];
  21. for(int j=0; j<n; j++){
  22. Arrays.fill(step[j],Integer.MAX_VALUE);
  23. }
  24.  
  25. for(int width=0; width<w; width++){
  26. for(int length=0; length<l; length++){
  27. if (room[width][length] == 'C'){
  28. rowStart = width;
  29. colStart = length;
  30. }
  31. if(room[width][length] == 'W'){
  32. rowEnd = width;
  33. colEnd = length;
  34. }
  35. if(room[width][length] == 'X'){
  36. step[width][length] = -1;
  37. }
  38. }
  39. }
  40. LinkedList<Integer> rowQueue = new LinkedList<Integer>();
  41. LinkedList<Integer> colQueue = new LinkedList<Integer>();
  42. rowQueue.add(rowStart);
  43. colQueue.add(colStart);
  44.  
  45. step[rowStart][colStart] = 0;
  46. while(!rowQueue.isEmpty()){
  47. int r = rowQueue.poll();
  48. int c = colQueue.poll();
  49. //top
  50. if(r-1>=0 && step[r-1][c]>step[r][c]+1){
  51. rowQueue.add(r-1);
  52. colQueue.add(c);
  53. if(step[r-1][c]!=-1) {
  54. step[r-1][c] = step[r][c] + 1;
  55. } else{
  56. step[r-1][c] = step[r][c];
  57. }
  58. }
  59.  
  60. //bot
  61. if(r+1<w && step[r+1][c]>step[r][c]+1){
  62. rowQueue.add(r+1);
  63. colQueue.add(c);
  64. if(step[r+1][c]!=-1) {
  65. step[r+1][c] = step[r][c] + 1;
  66. } else{
  67. step[r+1][c] = step[r][c];
  68. }
  69. }
  70.  
  71. //right
  72. if(c+1<l && step[r][c+1]>step[r][c]+1){
  73. rowQueue.add(r);
  74. colQueue.add(c+1);
  75. if(step[r][c+1]!=-1) {
  76. step[r][c+1] = step[r][c] + 1;
  77. } else{
  78. step[r][c+1] = step[r][c];
  79. }
  80. }
  81.  
  82. //left
  83. if(c-1>=0 && step[r][c-1]>step[r][c]+1){
  84. rowQueue.add(r);
  85. colQueue.add(c-1);
  86. if(step[r][c-1]!=-1) {
  87. step[r][c-1] = step[r][c] + 1;
  88. } else{
  89. step[r][c-1] = step[r][c];
  90. }
  91. }
  92. }
  93. if(step[rowEnd][colEnd]<=60){
  94. System.out.println(step[rowEnd][colEnd]);
  95. } else{
  96. System.out.println("#notworth");
  97. }
  98.  
  99. }
  100. }
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement