(Analysis by Nick Wu)

In this problem, Farmer John is mowing grass on a grid. He wants to figure out the largest period of time that exists such that Farmer John never mows the same square of grass twice within that amount of time.

Farmer John will mow at most one thousand squares of grass, so we can just keep track of the last point in time when Farmer John mowed the grass in a given square. We can store these times in a large two-dimensional array. As an implementation detail, because arrays do not support negative coordinates, we can pretend that Farmer John starts at the point (1000, 1000) and then simulate the mowing directly.

Here is my code demonstrating this.

import java.io.*;
import java.util.*;
public class mowing {
public static void main(String[] args) throws IOException {
// initialize file I/O
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("mowing.out")));

/*
* Create a two-dimensional array where lastTime[i][j] stores the last time
* that Farmer John visited point (i, j). If Farmer John has never visited that
* point, then lastTime[i][j] == -1.
*/
int[][] lastTime = new int[2001][2001];
for(int i = 0; i < lastTime.length; i++) {
for(int j = 0; j < lastTime[i].length; j++) {
lastTime[i][j] = -1;
}
}

// (currX, currY) is the point that Farmer John is currently at.
int currX = 1000;
int currY = 1000;
lastTime[currX][currY] = 0;
int currentTime = 0;

// the longest period of time cannot exceed 1000, so if it is still 1001, he never visits the same square twice.
int answer = 100 * 10 + 1;

for(int i = 0; i < n; i++) {
// read in the direction that Farmer John goes in
String direction = st.nextToken();
int dirX = 0;
int dirY = 0;
if(direction.equals("N")) {
dirX = -1;
}
else if(direction.equals("S")) {
dirX = 1;
}
else if(direction.equals("W")) {
dirY = -1;
}
else {
dirY = 1;
}
// read in the number of steps he travels
int numSteps = Integer.parseInt(st.nextToken());
// travel that many steps
for(int j = 1; j <= numSteps; j++) {
currX += dirX;
currY += dirY;
currentTime++;
// check if Farmer John has visited that square before, and the amount of time that has elapsed since then if valid
if(lastTime[currX][currY] >= 0 && currentTime - lastTime[currX][currY] < answer) {
}
lastTime[currX][currY] = currentTime;
}
}
// check if he has never visited the same square twice