제출 #1148066

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148066		tito_daynor	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	0 ms	328 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

class CoinCollector {
private:
    int N;
    vector<vector<int>> grid;
    vector<vector<bool>> visited;
    ll totalMoves;
    
    ll dfs(int x, int y, int targetX, int targetY) {
        if (x == targetX && y == targetY) {
            return 0;
        }
        
        visited[x][y] = true;
        ll minMoves = LLONG_MAX;
        
        vector<pair<int, int>> moves = {
            {x+1, y}, {x-1, y}, {x, y+1}, {x, y-1}
        };
        
        for (auto [nextX, nextY] : moves) {
            if (visited[nextX][nextY]) continue;
            
            ll currentDist = abs(nextX - targetX) + abs(nextY - targetY);
            
            if (currentDist < abs(x - targetX) + abs(y - targetY)) {
                ll moves = dfs(nextX, nextY, targetX, targetY);
                if (moves != LLONG_MAX) {
                    minMoves = min(minMoves, moves + 1);
                }
            }
        }
        
        visited[x][y] = false;
        return minMoves;
    }
    
public:
    ll solve(vector<pair<int, int>>& coins) {
        totalMoves = 0;
        N = coins.size() / 2;
        
        for (auto& [x, y] : coins) {
            if (x < 1) {
                totalMoves += 1 - x;
                x = 1;
            }
            if (x > N) {
                totalMoves += x - N;
                x = N;
            }
            if (y < 1) {
                totalMoves += 1 - y;
                y = 1;
            }
            if (y > 2) {
                totalMoves += y - 2;
                y = 2;
            }
        }
        
        visited.resize(N + 2, vector<bool>(3, false));
        
        set<int> usedCoins;
        for (int targetX = 1; targetX <= N; targetX++) {
            for (int targetY = 1; targetY <= 2; targetY++) {
                ll minMoves = LLONG_MAX;
                int bestCoin = -1;
                
                for (int i = 0; i < coins.size(); i++) {
                    if (usedCoins.count(i)) continue;
                    
                    for (auto& row : visited) {
                        fill(row.begin(), row.end(), false);
                    }
                    
                    ll moves = dfs(coins[i].first, coins[i].second, targetX, targetY);
                    if (moves < minMoves) {
                        minMoves = moves;
                        bestCoin = i;
                    }
                }
                
                totalMoves += minMoves;
                usedCoins.insert(bestCoin);
            }
        }
        
        return totalMoves;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    
    vector<pair<int, int>> coins(2*N);
    for (int i = 0; i < 2*N; i++) {
        cin >> coins[i].first >> coins[i].second;
    }
    
    CoinCollector solver;
    cout << solver.solve(coins) << "\n";
    
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63