You live in a city in which all roads are one-way. \"Streets\" run East/West, wh

Question

You live in a city in which all roads are one-way. "Streets" run East/West, while "Avenues" run North/South (for a visualization of this, look at any map of Manhattan). All streets and avenues are numbered: lower-numbered streets are furthest south, and lower-numbered avenues are furthest east. There are 100 "Streets" and 10 Avenues", so 1st Street and 1st Avenue is the most south-eastern point of the city, while 100th street and 10th avenue is the most north-western point of the city The odd-numbered Streets (1st Street, 3rd Street, etc) go from West to East, while even-numbered Streets go from East to West. Odd-numbered Avenues go from South to North, while even-numbered Avenues go from North to South For the purposes of simplicity, assume that the distance between two consecutive streets is the same as the distance between two consecutive avenues. We will refer to this distance as one "block" (or a "city-block") Project You are to write a Java program which asks the user to input in a starting position (a starting Street anda starting Avenue) and an ending position (a destination Street and a destination Avenue), and output a list of directions that one can take, by car, to go from the starting position to the ending position. Also output the total number of city-blocks traveled durng this trip

Explanation / Answer

import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; class Pair { // Representing the node as a pair int street, avenue; Pair(int street, int avenue) { this.street = street; this.avenue = avenue; } @Override public String toString() { return "(" + this.street + ", " + this.avenue + ")"; } } public class FindPath { // You can change these to any value you desire :) private static int streets = 1000; private static int avenues = 10; public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("Enter the source street: "); int sourceStreet = sc.nextInt(); System.out.print("Enter the source avenue: "); int sourceAvenue = sc.nextInt(); System.out.print("Enter the destination street: "); int destinationStreet = sc.nextInt(); System.out.print("Enter the destination avenue: "); int destinationAvenue = sc.nextInt(); // This parent stores the parent of ith street jth avenue as a pair again // Don't confuse with Pair[][]. It is just same as int[][] where int[][] contains integers and Pair[][] contains pairs Pair[][] parent = new Pair[streets + 1][avenues + 1]; // This is used to keep track of all visited nodes (or pairs), so that we visit them only once boolean visited[][] = new boolean[streets + 1][avenues + 1]; // At each level we keep track of the pairs (or nodes) that we are visiting List currentLevel = List.of(new Pair(sourceStreet, sourceAvenue)); // MainLoop is not a mistake. It is java loop name style :) MainLoop: while (currentLevel.size() > 0) { List nextLevel = new ArrayList(); for (int i = 0; i 1) list.add(new Pair(node.street - 1, node.avenue)); } else { if (node.street

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.