SHARE
TWEET

Untitled

a guest May 22nd, 2019 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.List;
  4. import java.util.Map;
  5. import java.util.PriorityQueue;
  6. import java.util.Scanner;
  7.  
  8. /**
  9.  * Generic class to represent a regular pair (C++ style).
  10.  *
  11.  * Use it for storing the indexes of a grid cell like this <row, col>.
  12.  */
  13. class Pair<T, U> {
  14.     public T first;
  15.     public U second;
  16.    
  17.     public Pair(T first, U second) {
  18.         this.first = first;
  19.         this.second = second;
  20.     }
  21.    
  22.     @Override
  23.     public boolean equals(Object other) {
  24.         Pair<T, U> p = (Pair<T, U>) other;
  25.        
  26.         return this.first.equals(p.first) && this.second.equals(p.second);
  27.     }
  28.    
  29.     @Override
  30.     public int hashCode() {
  31.         int result = this.first == null ? 0 : this.first.hashCode();
  32.         result = result * 31 + (this.second == null ? 0 : this.second.hashCode());
  33.         return result;  
  34.     }
  35.    
  36.     @Override
  37.     public String toString() {
  38.         return "<" + this.first + ", " + this.second + ">";
  39.     }
  40. }
  41.  
  42. /**
  43.  * Generic class to represent a tuple with three members.
  44.  *
  45.  * Use it to store cell to expand (whose row might be triTuple.second and col triTuple.third).
  46.  * triTuple.first (g + h) stores the cost associated with the cell defined by the last two members.
  47.  */
  48. class TriTuple<T, U, V> implements Comparable<TriTuple<T, U, V>> {
  49.     public T first;
  50.     public U second;
  51.     public V third;
  52.    
  53.     public TriTuple(T first, U second, V third) {
  54.         this.first = first;
  55.         this.second = second;
  56.         this.third = third;
  57.     }
  58.    
  59.     @Override
  60.     public boolean equals(Object other) {
  61.         TriTuple<T, U, V> t = (TriTuple<T, U, V>) other;
  62.        
  63.         return this.first.equals(t.first) && this.second.equals(t.second) && this.third.equals(t.third);
  64.     }
  65.    
  66.     @Override
  67.     public int hashCode() {
  68.         int result = this.first == null ? 0 : this.first.hashCode();
  69.         result = result * 31 + (this.second == null ? 0 : this.second.hashCode());
  70.         result = result * 31 + (this.third == null ? 0 : this.third.hashCode());
  71.         return result;  
  72.     }
  73.    
  74.     @Override
  75.     public int compareTo(TriTuple<T, U, V> other) {
  76.         return (Integer) this.first - (Integer) other.first;
  77.     }
  78.    
  79.     @Override
  80.     public String toString() {
  81.         return "<" + this.first + ", " + this.second + ", " + this.third + ">";
  82.     }
  83. }
  84.  
  85. public class Solution {
  86.     /**
  87.      * Generic method to print the grid.
  88.      *
  89.      * @param m         The matrix to display.
  90.      */
  91.     public static <T> void printMatrix(List<List<T>> m) {
  92.         System.out.println("Matrix contents:");
  93.         for (List<T> v : m) {
  94.             for (T x : v) {
  95.                 System.out.print(x);
  96.             }
  97.             System.out.println();
  98.         }
  99.         System.out.println();
  100.     }
  101.  
  102.     /**
  103.      * Generic method to print the path to a goal state.
  104.      *
  105.      * Each element in the path is a pair containing a matrix cell's row and col.
  106.      *
  107.      * @param path      The path to a goal state.
  108.      */
  109.     public static <T, U> void printPath(List<Pair<T, U>> path) {
  110.         System.out.println(path.size() - 1);
  111.         for (int i = path.size() - 1; i >= 0; i--) {
  112.             System.out.println(path.get(i).first + " " + path.get(i).second);
  113.         }
  114.     }
  115.  
  116.     /**
  117.      * Computes and returns the absolute value of an integer.
  118.      *
  119.      * @param a         Integer value to compute the absolute value for.
  120.      *
  121.      * @return          The absolute value of the integer supplied as input.
  122.      */
  123.     public static Integer abs(Integer a) {
  124.         return a < 0 ? -a : a;
  125.     }
  126.  
  127.     /**
  128.      * Manhattan distance heuristic used by A*.
  129.      *
  130.      * @param source    A cell in the matrix encoded as <row, col>.
  131.      * @param dest      A cell in the matrix encoded as <row, col>.
  132.      *
  133.      * @return          Manhattan distance between the two cells.
  134.      */
  135.     public static int h(Pair<Integer, Integer> source, Pair<Integer, Integer> dest) {
  136.         return abs(source.first - dest.first) + abs(source.second - dest.second);
  137.     }
  138.  
  139.     /**
  140.      * Method to retrieve a list of cells accesible from a given cell.
  141.      *
  142.      * @param M         Grid, encoded as a list of Characters.
  143.      * @param row       Row of the source cell.
  144.      * @param col       Column of the source cell.
  145.      *
  146.      * @return          A list containing at most four neighboring cells.
  147.      */
  148.     public static <T extends Character> List<Pair<Integer, Integer>> getNeighbors(List<List<T>> M, int row, int col) {
  149.         List<Pair<Integer, Integer>> ret = new ArrayList<>();
  150.  
  151.         if (row - 1 >= 0 && !M.get(row - 1).get(col).equals('%')) {
  152.             ret.add(new Pair<>(row - 1, col));
  153.         }
  154.  
  155.         if (row + 1 < M.size() && !M.get(row + 1).get(col).equals('%')) {
  156.             ret.add(new Pair<>(row + 1, col));
  157.         }
  158.  
  159.         if (col - 1 >= 0 && !M.get(row).get(col - 1).equals('%')) {
  160.             ret.add(new Pair<>(row, col - 1));
  161.         }
  162.  
  163.         if (col + 1 < M.get(row).size() && !M.get(row).get(col + 1).equals('%')) {
  164.             ret.add(new Pair<>(row, col + 1));
  165.         }
  166.  
  167.         return ret;
  168.     }
  169.  
  170.     /**
  171.      * Reconstructs the path from source to destination, based on the parents.
  172.      *
  173.      * @param n         Encoding of the destination cell.
  174.      * @param p         A mapping between each cell and its parent cell.
  175.      */
  176.     public static List<Pair<Integer, Integer>> buildPath(Pair<Integer, Integer> n, Map<Pair<Integer, Integer>, Pair<Integer, Integer>> p) {
  177.         List<Pair<Integer, Integer>> ret = new ArrayList<>();
  178.  
  179.         while (n.first != -1 && n.second != -1) {
  180.             ret.add(n);
  181.             n = p.get(n);
  182.         }
  183.  
  184.         return ret;
  185.     }
  186.  
  187.     /**
  188.      * Method to implement the A* algorithm.
  189.      *
  190.      * @param M         Encoding of the grid.
  191.      * @param rp        Pacman's starting row.
  192.      * @param cp        Pacman's starting column.
  193.      * @param rf        Food row.
  194.      * @param cf        Fool column.
  195.      *
  196.      * @return          The shortest path between Pacman and food, determined with A*.
  197.      *                  If no such path exists, returns an empty path.
  198.      */
  199.     public static <T extends Character> List<Pair<Integer, Integer>> astar(List<List<T>> M, int rp, int cp, int rf, int cf) {
  200.         PriorityQueue<TriTuple<Integer, Integer, Integer>> open = new PriorityQueue<>();
  201.         /*
  202.          * TODO: implement A*.
  203.          *       Use `open` for storing the next cell to expand, along with its total score (f = g + h).
  204.          *       Use `getNeighbors()` to retrieve the cells accessible from a given cell.
  205.          *       Use `buildPath()` to return the path from Pacman to food (once you found one path).
  206.          *       Use `h()` to estimate the cost from the current cell to the destination cell (you can try other heuristics too).
  207.          *       The `closed` set may be implemented as a hashMap, mapping each cell to its visited status (true or false).
  208.          *       The parent of each cell may be stored in a hashMap.
  209.          */
  210.  
  211.         return new ArrayList<Pair<Integer, Integer>>();
  212.     }
  213.  
  214.     public static void main(String[] args) {
  215.         int rp, cp;
  216.         int rf, cf;
  217.         int nr, nc;
  218.         char c;
  219.         Scanner s = new Scanner(System.in);
  220.  
  221.         rp = s.nextInt();
  222.         cp = s.nextInt();
  223.         rf = s.nextInt();
  224.         cf = s.nextInt();
  225.         nr = s.nextInt();
  226.         nc = s.nextInt();
  227.  
  228.         List<List<Character>> M = new ArrayList<>();
  229.  
  230.         for (int i = 0; i < nr; i++) {
  231.             List<Character> currentRow = new ArrayList<>();
  232.             String nextRow = s.next();
  233.             for (int j = 0; j < nc; j++) {
  234.                 currentRow.add(nextRow.charAt(j));
  235.             }
  236.             M.add(currentRow);
  237.         }
  238.  
  239.         s.close();
  240.         //printMatrix(M);
  241.         List<Pair<Integer, Integer>> path = astar(M, rp, cp, rf, cf);
  242.         printPath(path);
  243.     }
  244. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top