Analysis and Solution for Jan. 2016 USACO Bronze Problem 3

Mowing the Field

Link to problem statement

Analysis

FJ’s field can be thought of as an extremely large 2-D array, with -1 representing points that FJ has not visited yet. Because arrays do not support negative indicies, FJ starts at (1000, 1000) in the array. FJ starts mowing the field at time 0. For each step he takes, we find the difference in the time in the array and the current time, if the time in the array is not -1. We then put the current time in the array, and repeat for every step in FJ’s path.

Implementations

C++17

/* USACO January 2016 Bronze 3
 * C++17 code
 */
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
int lastVisit[2001][2001];
int main() {
    int N = 0, ans = 1001, x = 1000, y = 1000, t = 0, dx = 0, dy = 0, s = 0;
    string dir;
    ifstream input("mowing.in");
    ofstream output("mowing.out");
    for (int i = 0; i < 2001; i++){
        for (int j = 0; j < 2001; j++)
            lastVisit[i][j] = -1;
    }
    lastVisit[x][y] = 0;
    input >> N;
    for (int i = 0; i < N; i++){
        dx = 0;
        dy = 0;
        input >> dir;
        if (dir.compare("N") == 0)
            dy = 1;
        else if (dir.compare("S") == 0)
            dy = -1;
        else if (dir.compare("W") == 0)
            dx = -1;
        else
            dx = 1;
        input >> s;
        for (int j = 0; j < s; j++){
            x += dx;
            y += dy;
            t++;
             if (lastVisit[x][y] >= 0 && t - lastVisit[x][y] < ans)
                ans = t - lastVisit[x][y];
            lastVisit[x][y] = t;
        }
    }
    input.close();
    if (ans == 1001)
        ans = -1;
    output << ans << "\n";
    output.close();
    return 0;
}

Java 8

/* USACO January 2016 Bronze 3
 * Java 8 code
 */
import java.io.*;
import java.util.*;
public class Jan2016Bronze3{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("mowing.in"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("mowing.out")));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[][] lastVisit = new int[2001][2001];
        for (int i = 0; i < 2001; i++){
            for (int j = 0; j < 2001; j++)
                lastVisit[i][j] = -1;
        }
        int x = 1000;
        int y = 1000;
        lastVisit[x][y] = 0;
        int N = Integer.parseInt(st.nextToken());
        int dx;
        int dy;
        int t = 0;
        int s;
        int ans = 1001;
        String dir;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            dx = 0;
            dy = 0;
            dir = st.nextToken();
            switch (dir) {
                case "N":
                    dy = 1;
                    break;
                case "S":
                    dy = -1;
                    break;
                case "E":
                    dx = 1;
                    break;
                default:
                    dx = -1;
                    break;
            }
            s = Integer.parseInt(st.nextToken());
            for (int j = 0; j < s; j++) {
                x += dx;
                y += dy;
                t++;
                if (lastVisit[x][y] >= 0 && t - lastVisit[x][y] < ans)
                    ans = t - lastVisit[x][y];
                lastVisit[x][y] = t;
            }
            if (i != N - 1)
                st = new StringTokenizer(br.readLine());
        }
        br.close();
        if (ans == 1001){
            ans = -1;
        }
        pw.println(ans);
        pw.close();
    }
}

Written on June 19, 2018

Back