SRM646div1med:TheGridDivOne

問題:TopCoder Statistics - Problem Statement

解法:座標圧縮した後ダイクストラする。座標圧縮についてはよくわからなかったのでkmjpさんのコードを参考にさせていただきました。
以下ソースコード

struct Point {
    int y;
    int x;
    Point() {}
    Point(int y, int x) : y(y), x(x) {}
    bool operator<(const Point& rhs) const {
        return y <  rhs.y;
    }
};

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

const int MAXN = 200;
bool block[MAXN][MAXN];
int dist[MAXN][MAXN];

class TheGridDivOne {
public:
    int find(vector <int> x, vector <int> y, int k) {
        int n = x.size();
        /* 座標圧縮 */
        map<int, int> mx, my;
        mx[-1] = mx[0] = mx[1] = 0;
        my[-1] = my[0] = my[1] = 0;
        for (int i = 0; i < n; i++) {
            for (int d = -1; d <= 1; d++) {
                mx[x[i]+d] = 0;
                my[y[i]+d] = 0;
            }
        }
        vector<int> rx, ry;
        for (auto& el : mx) {
            el.second = rx.size();
            rx.push_back(el.first);
        }
        for (auto& el : my) {
            el.second = ry.size();
            ry.push_back(el.first);
        }
        memset(block, 0, sizeof(block));
        for (int i = 0; i < n; i++) {
            block[my[y[i]]][mx[x[i]]] = true;
        }
        rx.push_back(1<<30);
        ry.push_back(1<<30);
        /* dijkstra */
        for (int i = 0; i < MAXN; i++) for (int j = 0; j < MAXN; j++) dist[i][j] = 1<<30;
        Point start = Point(my[0], mx[0]);
        dist[start.y][start.x] = 0;
        priority_queue<pair<int, Point> > que;
        que.push(make_pair(0, start));
        while (!que.empty()) {
            auto now = que.top(); que.pop();
            Point p = now.second;
            int d = -now.first;
            if (d != dist[p.y][p.x]) continue;
            for (int i = 0; i < 4; i++) {
                int ny = p.y+dy[i], nx = p.x+dx[i];
                if (ny < 0 || ny >= ry.size() || nx < 0 || nx >= rx.size() || block[ny][nx]) continue;
                int distx = abs(rx[nx]-rx[p.x]), disty = abs(ry[ny]-ry[p.y]);
                if (d+distx+disty > k || dist[ny][nx] <= d+distx+disty) continue;
                dist[ny][nx] = d+distx+disty;
                que.push(make_pair(-dist[ny][nx], Point(ny, nx)));
            }
        }
        int ans = 0;
        for (int i = 0; i < ry.size(); i++) for (int j = 0; j < rx.size(); j++) {
            int rest = k-dist[i][j];
            if (rest < 0) continue;
            ans = max(ans, min(rx[j+1]-1, rx[j]+rest));
        }
        return ans;
    }
};