Last active
December 15, 2015 13:19
-
-
Save liezl200/5266586 to your computer and use it in GitHub Desktop.
This was a program my computer science teacher assigned. This was a fun one. He told us exactly how to do it, with some form or other of recursion, but I wanted to use stacks too for fun, and ended up coming up with a totally different solution to see if I could. At the time I wrote this, I was just obsessed with stacks for some reason...
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// LIEZL PUZON 2012 | |
import java.util.Stack; | |
import java.util.ArrayList; | |
public class shortestPath | |
{ | |
public static int[][] grid = {{1,1,1,1,1},{1,0,1,1,1},{1,0,1,1,1},{1,1,1,0,1},{0,0,0,0,1}}; | |
// the grid is hardcoded. 1 means that it's a valid location to travel. | |
// 0 means there's an obstacle there | |
// start in the upper left corner, grid[0][0] | |
/* | |
* 1 1 1 1 1 | |
* 1 0 1 1 1 | |
* 1 0 1 1 1 | |
* 1 1 1 0 1 | |
* 0 0 0 0 1 | |
*/ | |
// the shortest path is traced with 7's in the output | |
// you want to get to the bottom right corner. | |
public static boolean valid(int row, int column, int[][] grid) | |
{ | |
boolean result = false; | |
if(row>=0 && row < grid.length && column >=0 && column < grid[row].length) | |
if (grid[row][column] == 1) | |
result = true; | |
return result; | |
} | |
public static String toString(int[][] grid) | |
{ | |
String result = "\n"; | |
for (int row = 0; row< grid.length; row++) | |
{ | |
for (int column = 0; column < grid[row].length; column++) | |
result += grid[row][column] + ""; | |
result += "\n"; | |
} | |
return result; | |
} | |
public static void Traverse(int row, int col, Stack<String> path, ArrayList<Stack<String>> collected) | |
{ | |
// int minimal = grid.length + grid[0].length; | |
//how to implement this for more efficiency??? | |
//push current loc to stack | |
path.push(row +"," + col); | |
if (valid(row, col, grid)) | |
{ | |
// if complete, add a clone of the stack to the collected and then return. | |
// also if complete and stackSize = minimal, then return | |
if(row == grid.length-1 && col == grid[0].length -1) | |
collected.add((Stack<String>)path.clone()); | |
if (!path.contains((row + 1) +"," + col)) //new int[]{row + 1,col})) | |
Traverse(row+1, col, path, collected); //down | |
if (!path.contains(row + "," + (col + 1))) //new int[]{row,col + 1})) | |
Traverse(row, col + 1, path, collected); //right | |
if (!path.contains((row - 1) + "," + col)) // new int[]{row - 1,col})) | |
Traverse(row-1, col, path, collected); //up | |
if (!path.contains(row + "," + (col - 1))) //new int[]{row,col - 1})) | |
Traverse(row, col-1, path, collected); //left*/ | |
//must add code to pop ugly coordinates here or below | |
path.pop(); | |
} | |
else | |
{ | |
path.pop(); // go back 1 step and get rid of current square coordinates | |
return; | |
} | |
} | |
public static void trace(Stack<String> path) | |
{ | |
while(!path.isEmpty()) | |
{ | |
String coord = path.pop(); | |
grid[Integer.parseInt(coord.substring(0,1))][Integer.parseInt(coord.substring(2,3))] = 7; | |
} | |
} | |
public static void main(String[] args) | |
{ | |
ArrayList<Stack<String>> collected = new ArrayList<Stack<String>>(); | |
Stack<String> path = new Stack<String>(); | |
Traverse(0,0,path, collected); | |
if (collected.isEmpty()) | |
System.out.println("No paths from (0,0) to (" + (grid.length-1) + "," + (grid[0].length-1) + ")"); | |
else | |
{ | |
int min = 9999999; //sorry for the ugly sentinel | |
Stack<String> smallPath = new Stack<String>(); | |
for(int x = 0; x < collected.size(); x++) | |
{ | |
if (collected.get(x).size() < min) | |
{ | |
min = collected.get(x).size(); | |
smallPath = ((Stack<String>)collected.get(x).clone()); // put the copy that is smallest into smallPath | |
} | |
} | |
trace(smallPath); | |
System.out.println("Shortest Path:\n" + toString(grid)); | |
System.out.println("\nLength of Shortest Path: " + (min - 1)); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
java..
python?
CS212 !