Tractor1.txt

6
..x...
.x....
....x.
xx.x..
..x...
......

Tractor2.txt

5
.x.x.
.....
xxx..
....x
.x...

Tractor3.txt

10
..........
xxxxxxxx..
xxxxxxxx.x
xxxxxxx..x
xxxxxx..xx
xxxxx..xxx
xxxx..xxxx
xxx..xxxxx
xx..xxxxxx
xx........

Tractor4.txt

10
..xxxxxxxx
x..xxxxxxx
xx..xxxxxx
xxx..xxxxx
xxxx..xxxx
xxxxx..xxx
xxxxxx..xx
xxxxxxx..x
xxxxxxxx..
xxxxxxxxx.

TractorPath.java

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

/*
 * You just finished disking your field and it is time to head back to the 
 * farmhouse. Some of the livestock has been acting up (you think it is the 
 * Clydesdale horses but you’re not sure) and putting up obstacles to prevent 
 * you from getting home.
 *
 * Input: The first line contains a single positive integer, n, denoting the 
 * side length of the square field. The next n lines will consist of a map of 
 * your field, with ‘.’ denoting an open space and ‘x’ denoting an obstacle.
 * You are in the top left corner of the field and the farmhouse is in the 
 * bottom right corner of the field. You don’t have a lot of gas in the 
 * tractor, so each move you make must be either down or right (no 
 * backtracking). 
 * 
 * Output: Print “Yes” if there is a simple path (down and right moves only) 
 * to your farm house. If there is no simple path print “No”.
 */
public class TractorPath {

	public static void main(String[] args) throws FileNotFoundException {
		// For testing:
		File f = new File("C:\\Users\\chris\\Desktop\\Tractor4.txt");
		Scanner input = new Scanner(f);
		
		// For submission:
		//Scanner input = new Scanner(System.in); 

		// The first line contains a single positive integer, n, denoting the 
		// side length of the square field.
		int n = input.nextInt();
		
		// Right now I am just before the end of the first line, so I need to
		// move the scanner down to the second line by finishing reading this
		// line.
		input.nextLine();
		
		// Idea: I think I am going to have to look at the map multiple times
		// (like if I find there is an obstacle) so I better put the whole
		// thing in an array.
		char[][] map = new char[n][n];
		for (int y = 0; y < n; y++) {
			String line = input.nextLine();
			for (int x = 0; x < n; x++) {
				map[x][y] = line.charAt(x);
			}
		}

		// Idea: We'll explore right, then down, and don't revisit paths
		// we've already been too.
		char[][] visited = new char[n][n];
		int currentX = 0, currentY = 0;
		
		// while not in the bottom right corner
		while (currentX < n-1 || currentY < n-1) {
			visited[currentX][currentY] = 'V';
			// go right if we can and we haven't already visited it
			if (currentX+1 < n
					&& map[currentX+1][currentY] == '.'
					&& visited[currentX+1][currentY] != 'V')
				currentX++;
			// else go down if we can and haven't already visited it
			else if (currentY+1 < n
					&& map[currentX][currentY+1] == '.'
					&& visited[currentX][currentY+1] != 'V')
				currentY++;
			// Can't make progress, back track right if we can
			// But only if we visited it! as we're not allowed to go left or
			// up.
			else if (currentX > 0
					&& map[currentX-1][currentY] == '.'
					&& visited[currentX-1][currentY] == 'V')
				currentX--;
			// or up
			else if (currentY > 0 && map[currentX][currentY-1] == '.')
				currentY--;
			// if nowhere left to go, failed
			else
				break;
			
			// for debugging
			printBoard(currentX, currentY, map, visited);
		}
		
		if (currentX == n-1 && currentY == n-1)
			System.out.println("Yes");
		else
			System.out.println("No");
	}
	
	public static void printBoard(int currentX, int currentY, char[][] map, char[][] visited) {
		for (int y = 0; y < map.length; y++) {
			for (int x = 0; x < map.length; x++) {
				if (x == currentX && y == currentY)
					System.out.print('*');
				else if (visited[x][y] == 'V')
					System.out.print('V');
				else
					System.out.print(map[x][y]);
			}
			
			System.out.println();
		}
		
		System.out.println("x: " + currentX + ", y: " + currentY);
		System.out.println("------------");
	}
}