Advertisement
Guest User

Untitled

a guest
Nov 14th, 2019
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.83 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, colStart = 0, rowEnd = 0, colEnd = 0;
  12.  
  13.             for (int width = 0; width < w; width++) {
  14.                 room[width] = sc.next().toCharArray();
  15.             }
  16.  
  17.             int step[][] = new int[w][l];
  18.             for (int j = 0; j < n; j++) {
  19.                 Arrays.fill(step[j], Integer.MAX_VALUE);
  20.             }
  21.  
  22.             for (int width = 0; width < w; width++) {
  23.                 for (int length = 0; length < l; length++) {
  24.                     if (room[width][length] == 'C') {
  25.                         rowStart = width;
  26.                         colStart = length;
  27.                     }
  28.                     if (room[width][length] == 'W') {
  29.                         rowEnd = width;
  30.                         colEnd = length;
  31.                     }
  32.                     if (room[width][length] == 'X') {
  33.                         step[width][length] = -1;
  34.                     }
  35.                 }
  36.             }
  37.             LinkedList<Integer> rowQueue = new LinkedList<Integer>();
  38.             LinkedList<Integer> colQueue = new LinkedList<Integer>();
  39.             rowQueue.add(rowStart);
  40.             colQueue.add(colStart);
  41.  
  42.             step[rowStart][colStart] = 0;
  43.             while (!rowQueue.isEmpty()) {
  44.                 int r = rowQueue.poll();
  45.                 int c = colQueue.poll();
  46.                 //top
  47.                 if (r - 1 >= 0 && step[r - 1][c] > step[r][c] + 1) {
  48.                     rowQueue.add(r - 1);
  49.                     colQueue.add(c);
  50.                     step[r - 1][c] = step[r][c] + 1;
  51.                 }
  52.                 //bot
  53.                 if (r + 1 < w && step[r + 1][c] > step[r][c] + 1) {
  54.                     rowQueue.add(r + 1);
  55.                     colQueue.add(c);
  56.                     step[r + 1][c] = step[r][c] + 1;
  57.                 }
  58.  
  59.                 //right
  60.                 if (c + 1 < l && step[r][c + 1] > step[r][c] + 1) {
  61.                     rowQueue.add(r);
  62.                     colQueue.add(c + 1);
  63.                     step[r][c + 1] = step[r][c] + 1;
  64.                 }
  65.  
  66.                 //left
  67.                 if (c - 1 >= 0 && step[r][c - 1] > step[r][c] + 1) {
  68.                     rowQueue.add(r);
  69.                     colQueue.add(c - 1);
  70.                     step[r][c - 1] = step[r][c] + 1;
  71.                 }
  72.             }
  73.             if (step[rowEnd][colEnd] <= 60) {
  74.                 System.out.println(step[rowEnd][colEnd]);
  75.             } else {
  76.                 System.out.println("#notworth");
  77.             }
  78.             }
  79.         }
  80.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement