LillyPads.java

import java.util.ArrayList;
import java.util.Scanner;

/**Feb 20, 2014*/
//Period 4

public class LillyPads {
	public static void main(String args[]){
		Scanner kb = new Scanner(System.in);
		System.out.println("Data-points input:");
		String[] dims = kb.nextLine().split("\\s+"); //reads in dimensions
		char[][] m = new char[Integer.parseInt(dims[0])][Integer.parseInt(dims[1])];
		Location[][] grid = new Location[m.length][m[0].length];
		
		kb = new Scanner(System.in);
		System.out.println("Matrix input:");
		for(int i = 0; i < m.length; i++){  //reads in matrix to 2 dimensional char array
			m[i] = kb.nextLine().toCharArray();
		}

		for(int j = 0; j < grid.length; j++){ //converts character array to Location objects to store visited booleans/coordinates
			for(int h = 0; h < grid[0].length; h++){
				grid[j][h] = new Location(m[j][h], j, h, false);
			}
		}

		int[] s = findStart(m); //gets the initial location

		Location start = grid[s[0]][s[1]];
		start.visited = true;
		// Call the recursive method
		if(pathExists(start, grid)){
			System.out.print("A path exists.");
		}
		else{
			System.out.print("No path exists.");
		}
	}


	//recursively determines if a path exists from S to F
	public static boolean pathExists(Location loc, Location[][] grid){
		ArrayList<Location> adjLocs = getAdjLocs(loc, grid);
		
		//System.out.println("Current Location: (" + loc.getX() +", " + loc.getY() + ")");

		//returns true if location is adjacent to an F : BASE CASE
		for(int i = 0; i < adjLocs.size(); i++){
			if(adjLocs.get(i).getLetter() == 'F'){
				//System.out.println("Frog is adjacent to an F");
				adjLocs.get(i).visited = true;
				//System.out.println("!!!!!!!! END !!!!!!!!!!");
				return true;
			}
		}

		boolean found = false;
		//recurses through all adjacent nonvisited Os
		for(int i = 0; i < adjLocs.size() && !found; i++){
		        // If there is an unvisited o, then go recurse to it
		        if(adjLocs.get(i).getLetter() == 'O' && !adjLocs.get(i).visited()){
				//System.out.println("Frog is adjacent to an unvisited O; recursing\n");
				grid[loc.getX()][loc.getY()].visited = true;
				// If the O called bellow this level return true then we can stop
				found = pathExists(adjLocs.get(i), grid);
			}
		}
		// Return if we have found a F or not
		return found;
	}

	//returns an arraylist of the adjacent locations on the grid
	public static ArrayList<Location> getAdjLocs(Location loc, Location[][] grid){
		ArrayList<Location> locReturn = new ArrayList<Location>();
		int x = loc.getX()-1;
		int y = loc.getY()-1;
		
		for(int i = 0; i < 3; i++){
			for(int j = 0; j < 3; j++){
				if(!(x == loc.getX() && y == loc.getY()) && (x >= 0 && x < grid.length) && (y >= 0 && y < grid[0].length)){
					locReturn.add(grid[x][y]);
					//System.out.println("Added: " + grid[x][y].getLetter() + "(" + x + ", " + y + ")");
				}
				y++;
			}
			y = loc.getY()-1;
			x++;
		}
		
		//System.out.println("adjLocs length: " + locReturn.size());
		return locReturn;
	}

	//returns x and y value of start location
	public static int[] findStart(char[][] m){
		int[] ret = new int[2];
		for(int i = 0; i < m.length; i++){
			for(int j = 0; j < m[i].length; j++){
				if(m[i][j] == 'S'){
					ret[0] = i;
					ret[1] = j;
					return ret;
				}
			}
		}
		return null;
	}


}