USACO 2016 January Contest Gold Division - Radio Contact

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The problem can be solved with dynamic programming. For each possible position of Farmer John and Bessie we can compute the minimum energy required for them to both get to their end position by trying to step FJ forward, step Bessie forward, our move them both forward.

Source code

The source code in C++ can be seen below.

#include <cstdio>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

long long dist2(int x1, int y1, int x2, int y2) {
    long long dx = x1 - x2;
    long long dy = y1 - y2;
    return dx * dx + dy * dy;
}

int main() {
    ifstream cin("radio.in");
    ofstream cout("radio.out");

    int N, M;
    cin >> N >> M;

    int fx, fy, bx, by;
    cin >> fx >> fy;
    cin >> bx >> by;

    string s, t;
    cin >> s >> t;

    vector<pair<int, int>> F(N + 1), B(M + 1);
    F[0] = {fx, fy};
    for (int i = 1; i <= N; i++) {
        F[i] = F[i - 1];
        char c = s[i - 1];
        if (c == 'N')
            F[i].second++;
        else if (c == 'S')
            F[i].second--;
        else if (c == 'E')
            F[i].first++;
        else
            F[i].first--;
    }
    B[0] = {bx, by};
    for (int j = 1; j <= M; j++) {
        B[j] = B[j - 1];
        char c = t[j - 1];
        if (c == 'N')
            B[j].second++;
        else if (c == 'S')
            B[j].second--;
        else if (c == 'E')
            B[j].first++;
        else
            B[j].first--;
    }

    const long long INF = (1LL << 62);
    vector<vector<long long>> dp(N + 1, vector<long long>(M + 1, INF));
    dp[0][0] = 0;

    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= M; j++) {
            if (i == 0 && j == 0)
                continue;
            long long c = dist2(F[i].first, F[i].second, B[j].first, B[j].second);
            if (i > 0)
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + c);
            if (j > 0)
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + c);
            if (i > 0 && j > 0)
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + c);
        }
    }

    cout << dp[N][M] << '\n';
    return 0;
}