USACO 3.3 Camelot

Interesting problem… thinking this way:

• What would be the final meeting point? Hard to tell so let’s do a search for every point on the grid.
• What if there is no king? Then it’s much easier, we just need to find a point whose sum of steps to all the knights is minimum. This could be done by doing BFS starting from each knight, and ending at the desired point. Since we don’t know what the desired point is, the target is the entire grid.
• Now add king into the picture. King has interesting property that he does not cost any steps if with at least one knights. There are two cases here: first, the king might walk himself to the final meeting point; and second, there might be one or more knights that pick up the king at certain point and then head to meeting point together.
• So how to find that certain point where a king might be picked up by a knight? Hard to tell again so let’s do a search for every point on the grid… err that is not good, and will timeout. Interestingly, it turns out that for the test data, this pick up location is within 2 or 3 steps at most from where the king initially was, so we can cut the search space. Not sure if this can be proved though…

#include <vector>
#include <iostream>
#include <fstream>
#include <queue>
#include <climits>
#include <cstring>

using namespace std;

int R, C;
int sum[32][32];
int dist[32][32][32][32];
struct Node {
    int x, y, d;
    Node(int x, int y, int d) : x(x), y(y), d(d) {}
};
vector<Node> knights;
Node king(0, 0, 0);
int x, y;
char yc;

bool onGrid(int x, int y) {
    if (x < 1 || y < 1 || x > R || y > C) return false;
    return true;
}

void knightBFS(Node k) {
    queue<Node> q;
    q.push(k);
    int sx = k.x, sy = k.y;
    int dx[] = {2, 2, -2, -2, 1, -1, 1, -1};
    int dy[] = {1, -1, 1, -1, 2, 2, -2, -2};
    
    while (!q.empty()) {
        auto node = q.front();
        q.pop();
        int x = node.x, y = node.y;
        dist[x][y][x][y] = 0;
        for (int i = 0; i < 8; ++i) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (!onGrid(xx, yy)) continue;
            if (dist[sx][sy][xx][yy] != -1) continue;
            q.emplace(Node(xx, yy, node.d + 1));
            dist[sx][sy][xx][yy] = node.d + 1;
        }
    }
}

int main() {
    ifstream fin("camelot.in");
    ofstream fout("camelot.out");
    fin >> R >> C;
    bool kingFound = false;
    while (fin >> yc >> x) {
        y = yc - 'A' + 1;
        if (!kingFound) {
            king = Node(x, y, 0);
            kingFound = true;
        } else {
            knights.emplace_back(Node(x, y, 0));
        }
    }
    
    memset(dist, -1, sizeof(dist));
    memset(sum, 0, sizeof(sum));
    
    for (int i = 1; i <= R; ++i) {
        for (int j = 1; j <= C; ++j) {
            knightBFS(Node(i, j, 0));
        }
    }

    for (auto &knight : knights) {
        for (int i = 1; i <= R; ++i) {
            for (int j = 1; j <= C; ++j) {
                sum[i][j] += dist[knight.x][knight.y][i][j];
            }
        }
    }

    int ans = INT_MAX;
    const int MAX_STEP = 3;
    for(int i = 1; i <= R; ++i) {
        for(int j = 1; j <= C; ++j) {
            for(int dx = -MAX_STEP; dx <= MAX_STEP; ++dx) {
                for(int dy = -MAX_STEP; dy <= MAX_STEP; ++dy) {
                    for(auto &knight : knights) {
                        if (!onGrid(king.x + dx, king.y + dy)) continue;
                        int kx = knight.x, ky = knight.y;
                        int d1 = dist[king.x + dx][king.y + dy][i][j],
                        d2 = dist[kx][ky][king.x + dx][king.y + dy];
                        if (d1 == -1 || d2 == -1) continue;
                        
                        int distance = sum[i][j] -dist[kx][ky][i][j] + d1 + d2
                        + std::max(abs(dx),abs(dy));
                        ans = std::min(distance, ans);
                    }
                }
            }
        }
    }
    
    for(int i = 1; i <= R; ++i) {
        for(int j = 1;j<= C; ++j) {
            if (sum[i][j] < 0) continue;
            ans = min(sum[i][j] + max(abs(i - king.x), abs(j - king.y)),ans);
        }
    }
    
    cout << ans << endl;
    fout << ans << endl;
}