Submission #1173364

---

Source Code Expand

#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

struct State {
    int turn;
    int dist;
    int x[450];
    int y[450];
    
    double get_score() {
        return 1e7 / (dist * (10 + turn * 0.01));
    }
};

const int C = 10;
int H, W, K, T;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
char direction[5] = "RDLU";
int dest_x[450];
int dest_y[450];
bool used[30][30];

void solve(State &state) {
    int i, j, k, l;
    double best_score = state.get_score();
    vector <string> ans;
    vector <int> order;
    
    for (i = 0; i < K; i++) order.push_back(i);
    
    for (i = 0; i < T; i++) {
        double next_score = best_score;
        State next_state;
        string next_movement;
        
        for (j = 0; j < C; j++) {
            random_shuffle(order.begin(), order.end());
            
            for (k = 0; k < H; k++) {
                for (l = 0; l < W; l++) {
                    used[k][l] = false;
                }
            }
            
            for (k = 0; k < K; k++) used[state.x[k]][state.y[k]] = true;
            
            int move_dist = 0;
            string movement = string(K, '-');
            
            for (k = 0; k < K; k++) {
                int pos = order[k];
                
                for (l = 0; l < 4; l++) {
                    int x = state.x[pos];
                    int y = state.y[pos];
                    int nx = x + dx[l];
                    int ny = y + dy[l];
                    
                    if (nx < 0 || nx >= H || ny < 0 || ny >= W || used[nx][ny] == true) continue;
                    
                    if (abs(x - dest_x[pos]) + abs(y - dest_y[pos]) > abs(nx - dest_x[pos]) + abs(ny - dest_y[pos])) {
                        used[nx][ny] = true;
                        state.x[pos] = nx;
                        state.y[pos] = ny;
                        move_dist++;
                        movement[pos] = direction[l];
                        
                        break;
                    }
                }
            }
            
            state.turn++;
            state.dist -= move_dist;
            
            double score = state.get_score();
            if (score > next_score) {
                next_score = score;
                next_state = state;
                next_movement = movement;
            }
            
            state.turn--;
            state.dist += move_dist;
            
            for (k = 0; k < K; k++) {
                if (movement[k] == '-') continue;
                if (movement[k] == 'R') {
                    state.y[k]--;
                } else if (movement[k] == 'D') {
                    state.x[k]--;
                } else if (movement[k] == 'L') {
                    state.y[k]++;
                } else {
                    state.x[k]++;
                }
            }
        }
        
        if (next_score > best_score) {
            best_score = next_score;
            state = next_state;
            ans.push_back(next_movement);
        }
    }
    
    printf("%d\n", ans.size());
    for (i = 0; i < ans.size(); i++) printf("%s\n", ans[i].c_str());
}

int main() {
    int i;
    
    scanf("%d %d %d %d", &H, &W, &K, &T);
    
    State state;
    state.turn = 0;
    state.dist = 20;
    
    for (i = 0; i < K; i++) {
        int a, b, c, d;
        
        scanf("%d %d %d %d", &a, &b, &c, &d);
        
        a--;
        b--;
        c--;
        d--;
        
        state.x[i] = a;
        state.y[i] = b;
        
        dest_x[i] = c;
        dest_y[i] = d;
        
        state.dist += abs(a - c) + abs(b - d);
    }
    
    solve(state);
    
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void solve(State&)’:
./Main.cpp:112:30: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::vector<std::basic_string<char> >::size_type {aka long unsigned int}’ [-Wformat=]
     printf("%d\n", ans.size());
                              ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:119:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &H, &W, &K, &T);
                                         ^
./Main.cpp:128:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &a, &b, &c, &d);
                                             ^

Judge Result