fork download
copy 
  1.  
  2. import java.util.ArrayList;
  3. /**
  4.  * A robot is located in the upper-left corner of a 4×4 grid. 
  5.  * The robot can move either up, down, left, or right, but cannot go to the same location twice. 
  6.  * The robot is trying to reach the lower-right corner of the grid. 
  7.  * This program prints the number of unique ways to reach the destination.
  8.  * @author Felipe Ronderos
  9.  */
  10. public class Main {
  11.     public static void main(String[] args) {
  12.         Integer maxX, maxY;
  13.         //set the dimensions of the grid to 4 by 4
  14.         maxX = maxY = 7;
  15.         //An ArrayList used as a Queue
  16.         ArrayList<PartialSolution> partialSolutions = new ArrayList<>();
  17.         ArrayList<PartialSolution> finalSolutions = new ArrayList<>();
  18.         //initial position
  19.         Position<Integer> start = new Position<>(0,0);
  20.         ArrayList<Position<Integer>> startVisited = new ArrayList<Position<Integer>>();
  21.         startVisited.add(start);
  22.         partialSolutions.add(new PartialSolution(startVisited,start));
  23.         //final position
  24.         Position<Integer> end = new Position<>(maxX-1,maxY-1);
  25.         //Partial solutions are popped off the queue and replaced by possible solitions with the same path
  26.         while (partialSolutions.size()>0){
  27.             PartialSolution currentPath = partialSolutions.remove(0);
  28.             Position<Integer> last = currentPath.current;
  29.             Position<Integer> next;
  30.             ArrayList<Position<Integer>> visited;
  31.             if (last.getX()+1 < maxX){
  32.                 next = new Position<Integer>(last.getX()+1,last.getY());
  33.                 if (!currentPath.visited.contains(next)){
  34.                     visited = new ArrayList<>(currentPath.visited);
  35.                     visited.add(next);
  36.                     if (next.equals(end))
  37.                         finalSolutions.add(new PartialSolution(visited,next));
  38.                     else {
  39.                         partialSolutions.add(new PartialSolution(visited,next));
  40.                     }
  41.                 }
  42.             }
  43.             if (last.getY()+1 < maxY){
  44.                 next = new Position<Integer>(last.getX(),last.getY()+1);
  45.                 if (!currentPath.visited.contains(next)){
  46.                     visited = new ArrayList<>(currentPath.visited);
  47.                     visited.add(next);
  48.                     if (next.equals(end))
  49.                         finalSolutions.add(new PartialSolution(visited,next));
  50.                     else {
  51.                         partialSolutions.add(new PartialSolution(visited,next));
  52.                     }
  53.                 }
  54.             }
  55.             if (last.getX()-1 > -1){
  56.                 next = new Position<Integer>(last.getX()-1,last.getY());
  57.                 if (!currentPath.visited.contains(next)){
  58.                     visited = new ArrayList<>(currentPath.visited);
  59.                     visited.add(next);
  60.                     if (next.equals(end))
  61.                         finalSolutions.add(new PartialSolution(visited,next));
  62.                     else {
  63.                         partialSolutions.add(new PartialSolution(visited,next));
  64.                     }
  65.                 }
  66.             }
  67.             if (last.getY()-1 > -1){
  68.                 next = new Position<Integer>(last.getX(),last.getY()-1);
  69.                 if (!currentPath.visited.contains(next)){
  70.                     visited = new ArrayList<>(currentPath.visited);
  71.                     visited.add(next);
  72.                     if (next.equals(end))
  73.                         finalSolutions.add(new PartialSolution(visited,next));
  74.                     else {
  75.                         partialSolutions.add(new PartialSolution(visited,next));
  76.                     }
  77.                 }
  78.             }
  79.         }
  80.         System.out.println("There are " +finalSolutions.size()+" unique paths");
  81.     }
  82.     private static class PartialSolution{
  83.         ArrayList<Position<Integer>> visited;
  84.         Position<Integer> current;
  85.         PartialSolution(ArrayList<Position<Integer>> visited,Position<Integer> current){
  86.             this.current = current;
  87.             this.visited = visited;
  88.         }
  89.     }
  90.     private static class Position<A>{
  91.         A x,y;
  92.         Position(A x,A y){
  93.             this.x = x;
  94.             this.y = y;
  95.         }
  96.         public A getX() {
  97.             return x;
  98.         }
  99.         public A getY() {
  100.             return y;
  101.         }
  102.         @Override
  103.         public boolean equals(Object o) {
  104.             if (this == o) return true;
  105.             if (o == null || getClass() != o.getClass()) return false;
  106.             Position<?> position = (Position<?>) o;
  107.             if (!getX().equals(position.getX())) return false;
  108.             return getY().equals(position.getY());
  109.         }
  110.         @Override
  111.         public int hashCode() {
  112.             int result = getX().hashCode();
  113.             result = 31 * result + getY().hashCode();
  114.             return result;
  115.         }
  116.     }
  117. }
Time limit exceeded #stdin #stdout 5s 4386816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lcokSw
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!