Advertisement
Arham-4

BFS Solution

Jan 11th, 2018
210
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.89 KB | None | 0 0
  1. import java.util.*;
  2. public class Main{
  3.    
  4.     private static HashMap<Integer, Node> nodes = new HashMap<>();
  5.     private static HashMap<Coord, Integer> nodeCoords = new HashMap<>();
  6.    
  7.     // [y][x] not [x][y]
  8.     private static String[][] grid = null;
  9.     private static Node start = null;
  10.     private static Node goal = null;
  11.    
  12.     private static class Coord {
  13.         int x, y;
  14.        
  15.         Coord(int x, int y) {
  16.             this.x = x;
  17.             this.y = y;
  18.         }
  19.        
  20.         @Override
  21.         public boolean equals(Object object) {
  22.             if (!(object instanceof Coord)) {
  23.                 return false;
  24.             }
  25.    
  26.             Coord otherCoord = (Coord) object;
  27.             return this.x == otherCoord.x && this.y == otherCoord.y;
  28.         }
  29.  
  30.         @Override
  31.         public int hashCode() {
  32.             int result = 17;
  33.             result = 31 * result + Integer.valueOf(this.x).hashCode();
  34.             result = 31 * result + Integer.valueOf(this.y).hashCode();
  35.             return result;
  36.         }
  37.     }
  38.    
  39.     public static void main(String[] args){
  40.         Scanner scanner = new Scanner(System.in);
  41.         int cases = scanner.nextInt();
  42.         scanner.nextLine();
  43.         int counter = 0;
  44.         for (int i = 0; i < cases; i++) {
  45.             int rows = scanner.nextInt();
  46.             int columns = scanner.nextInt();
  47.             scanner.nextLine();
  48.             grid = new String[rows][columns];
  49.             for (int y = 0; y < grid.length; y++) {
  50.                 String[] line = scanner.nextLine().split("");
  51.                 for (int x = 0; x < grid[y].length; x++) {
  52.                     grid[y][x] = line[x];
  53.                     if (!line[x].equals("#")) {
  54.                         counter++;
  55.                         Node node = new Node(counter, x, y);
  56.                         if (line[x].equals("X")) {
  57.                             goal = node;
  58.                         } else if (line[x].equals("@")) {
  59.                             start = node;
  60.                         }
  61.                         nodes.put(node.id, node);
  62.                         nodeCoords.put(new Coord(x, y), node.id);
  63.                     }
  64.                 }
  65.             }
  66.             performProgram();
  67.             retracePath(goal);
  68.             for (int y = 0; y < grid.length; y++) {
  69.                 for (int x = 0; x < grid[y].length; x++) {
  70.                     System.out.print(grid[y][x]);
  71.                 }
  72.                 System.out.println();
  73.             }
  74.         }
  75.        
  76.     }
  77.    
  78.     private static void performProgram() {
  79.         LinkedList<Node> nextToVisit = new LinkedList<>();
  80.         HashSet<Integer> visited = new HashSet<>();
  81.         Node previous = start;
  82.        
  83.         for (Integer integer : nodes.keySet()) {
  84.             addAdjacentNodes(nodes.get(integer));
  85.         }
  86.        
  87.         nextToVisit.add(start);
  88.         while (!nextToVisit.isEmpty()) {
  89.             Node node = nextToVisit.remove();
  90.            
  91.             if (node == goal) {
  92.                 return;
  93.             }
  94.            
  95.             visited.add(node.id);
  96.             for (Node child : node.adjacent) {
  97.                 if (!visited.contains(child.id)) {
  98.                     nextToVisit.add(child);
  99.                     child.previous = node;
  100.                 }
  101.             }
  102.         }
  103.     }
  104.    
  105.     private static void retracePath(Node node) {
  106.         if (node != null) {
  107.             grid[node.y][node.x] = (node.id == start.id) ? "@" : (node.id == goal.id) ? "X" : ".";
  108.             retracePath(node.previous);
  109.         }
  110.     }
  111.    
  112.     private static void addAdjacentNodes(Node node) {
  113.         int[][] checks = {
  114.             {-1, 0},
  115.             {1, 0},
  116.             {0, 1},
  117.             {0, -1},
  118.         };
  119.         for (int i = 0; i < checks.length; i++) {
  120.             if (isLegal(node.x + checks[i][0], node.y + checks[i][1])) {
  121.                 Node otherNode = getNode(node.x + checks[i][0], node.y + checks[i][1]);
  122.                 if (otherNode != null) {
  123.                     addEdge(node.id, otherNode.id);
  124.                 }
  125.             }
  126.         }
  127.     }
  128.    
  129.     private static Node getNode(int x, int y) {
  130.         return nodes.get(nodeCoords.get(new Coord(x, y)));
  131.     }
  132.    
  133.     private static Node getNode(int id) {
  134.         return nodes.get(id);
  135.     }
  136.    
  137.     private static void addEdge(int source, int destination) {
  138.         getNode(source).adjacent.add(getNode(destination));
  139.     }
  140.    
  141.     private static class Node {
  142.         int id;
  143.         int x,y;
  144.         LinkedList<Node> adjacent = new LinkedList<>();
  145.         Node previous = null;
  146.         Node(int id, int x, int y) {
  147.             this.id = id;
  148.             this.x = x;
  149.             this.y = y;
  150.         }
  151.     }
  152.    
  153.     private static boolean isLegal(int x, int y) {
  154.         return x >= 0 && x < grid[0].length && y >= 0 && y < grid.length && !grid[y][x].equals("#");
  155.     }
  156. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement