Skip to content

Instantly share code, notes, and snippets.

@cbilson
Created February 6, 2018 12:08
Show Gist options
  • Save cbilson/8fd009c97012c16ca70b5c1d8ae95c1c to your computer and use it in GitHub Desktop.
Save cbilson/8fd009c97012c16ca70b5c1d8ae95c1c to your computer and use it in GitHub Desktop.
6
..x...
.x....
....x.
xx.x..
..x...
......
5
.x.x.
.....
xxx..
....x
.x...
10
..........
xxxxxxxx..
xxxxxxxx.x
xxxxxxx..x
xxxxxx..xx
xxxxx..xxx
xxxx..xxxx
xxx..xxxxx
xx..xxxxxx
xx........
10
..xxxxxxxx
x..xxxxxxx
xx..xxxxxx
xxx..xxxxx
xxxx..xxxx
xxxxx..xxx
xxxxxx..xx
xxxxxxx..x
xxxxxxxx..
xxxxxxxxx.
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("------------");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment