Submission #65224589

---

Source Code Expand

// 方針:Sa15MiyagiJapan, Coding(主):ChatGPT o4-mini (副, サンプル):Sa15MiyagiJapan.

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

using pii = pair<int,int>;
const int INF = 1e9;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;
    vector<pii> target(M);
    for(int i = 0; i < M; i++) cin >> target[i].first >> target[i].second;

    // Directions: U D L R
    const vector<int> di = {-1, 1, 0, 0};
    const vector<int> dj = {0, 0, -1, 1};
    const vector<char> dch = {'U','D','L','R'};

    vector<vector<bool>> blocked(N, vector<bool>(N, false));
    
    int now_i = target[0].first;
    int now_j = target[0].second;
    int k = 1;
    vector<pair<char,char>> ans;

    // slide helper
    auto slide_to = [&](int si, int sj, int dir){
        int ci = si, cj = sj;
        while(true){
            int ni = ci + di[dir], nj = cj + dj[dir];
            if(ni<0||ni>=N||nj<0||nj>=N||blocked[ni][nj]) break;
            ci = ni; cj = nj;
        }
        return make_pair(ci, cj);
    };

    while(k < M){
        struct Pat{int type, dir;};
        vector<Pat> patterns;
        // no-op
        patterns.push_back({-1,-1});
        // toggle neighbors
        for(int d=0; d<4; d++){
            int ni = now_i + di[d], nj = now_j + dj[d];
            if(ni>=0&&ni<N&&nj>=0&&nj<N) patterns.push_back({d, d});
        }

        int best_cost = INF;
        Pat best_p;

        // Evaluate each pattern by sum of BFS distances to all remaining targets
        for(auto &p : patterns){
            // apply toggle
            if(p.type >= 0){
                int bi = now_i + di[p.dir], bj = now_j + dj[p.dir];
                blocked[bi][bj] = !blocked[bi][bj];
            }

            int total_cost = (p.type>=0 ? 1 : 0);
            bool possible = true;
            // accumulate cost from current segment k..M-1
            for(int seg = k; seg < M; seg++){
                // BFS from start (now or previous target)
                int si = (seg == k ? now_i : target[seg-1].first);
                int sj = (seg == k ? now_j : target[seg-1].second);
                int ei = target[seg].first, ej = target[seg].second;
                
                vector<vector<int>> dist(N, vector<int>(N, INF));
                deque<pii> dq;
                dist[si][sj] = 0;
                dq.emplace_back(si, sj);
                int seg_cost = INF;

                while(!dq.empty()){
                    auto [ci, cj] = dq.front(); dq.pop_front();
                    int cd = dist[ci][cj];
                    if(ci == ei && cj == ej){ seg_cost = cd; break; }
                    // move
                    for(int d=0; d<4; d++){
                        int ni = ci+di[d], nj = cj+dj[d];
                        if(ni<0||ni>=N||nj<0||nj>=N||blocked[ni][nj]) continue;
                        if(dist[ni][nj] > cd+1){ dist[ni][nj] = cd+1; dq.emplace_back(ni,nj); }
                    }
                    // slide
                    for(int d=0; d<4; d++){
                        auto [ti2, tj2] = slide_to(ci, cj, d);
                        if(ti2==ci && tj2==cj) continue;
                        if(dist[ti2][tj2] > cd+1){ dist[ti2][tj2] = cd+1; dq.emplace_back(ti2,tj2); }
                    }
                }
                if(seg_cost == INF){ possible = false; break; }
                total_cost += seg_cost;
                if(total_cost >= best_cost) break; // prune
            }

            if(possible && total_cost < best_cost){
                best_cost = total_cost;
                best_p = p;
            }
            // revert toggle
            if(p.type >= 0){
                int bi = now_i + di[p.dir], bj = now_j + dj[p.dir];
                blocked[bi][bj] = !blocked[bi][bj];
            }
        }

        // Apply best pattern
        if(best_p.type >= 0){
            int bi = now_i + di[best_p.dir], bj = now_j + dj[best_p.dir];
            blocked[bi][bj] = !blocked[bi][bj];
            ans.emplace_back('A', dch[best_p.dir]);
        }

        // BFS one-step for next target k
        vector<vector<bool>> vis(N, vector<bool>(N,false));
        vector<vector<pair<char,char>>> first(N, vector<pair<char,char>>(N, {'?','?'}));
        deque<pii> dq;
        vis[now_i][now_j] = true;
        dq.emplace_back(now_i, now_j);
        pii goal = target[k];
        while(!dq.empty()){
            auto [ci, cj] = dq.front(); dq.pop_front();
            if(ci == goal.first && cj == goal.second) break;
            int cd = 0; // unused
            // move
            for(int d=0; d<4; d++){
                int ni = ci+di[d], nj = cj+dj[d];
                if(ni<0||ni>=N||nj<0||nj>=N||blocked[ni][nj]) continue;
                if(!vis[ni][nj]){
                    vis[ni][nj] = true;
                    first[ni][nj] = (ci==now_i && cj==now_j) ? make_pair('M',dch[d]) : first[ci][cj];
                    dq.emplace_back(ni,nj);
                }
            }
            // slide
            for(int d=0; d<4; d++){
                auto [ti2, tj2] = slide_to(ci, cj, d);
                if(ti2==ci && tj2==cj) continue;
                if(!vis[ti2][tj2]){
                    vis[ti2][tj2] = true;
                    first[ti2][tj2] = (ci==now_i && cj==now_j) ? make_pair('S',dch[d]) : first[ci][cj];
                    dq.emplace_back(ti2,tj2);
                }
            }
        }
        auto [act, dchar] = first[goal.first][goal.second];
        ans.emplace_back(act, dchar);
        if(act=='M'){
            for(int d=0; d<4; d++) if(dch[d]==dchar){ now_i+=di[d]; now_j+=dj[d]; break; }
        } else {
            for(int d=0; d<4; d++) if(dch[d]==dchar){ auto p = slide_to(now_i, now_j, d); now_i=p.first; now_j=p.second; break; }
        }
        if(now_i == target[k].first && now_j == target[k].second) k++;
    }

    // Output answer
    for(auto &pr : ans) cout << pr.first << " " << pr.second << "\n";
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:128:17: warning: unused variable ‘cd’ [-Wunused-variable]
  128 |             int cd = 0; // unused
      |                 ^~
Main.cpp:113:43: warning: ‘best_p.main()::Pat::dir’ may be used uninitialized [-Wmaybe-uninitialized]
  113 |             int bi = now_i + di[best_p.dir], bj = now_j + dj[best_p.dir];
      |                                           ^
Main.cpp:53:13: note: ‘best_p.main()::Pat::dir’ was declared here
   53 |         Pat best_p;
      |             ^~~~~~
Main.cpp:112:9: warning: ‘best_p.main()::Pat::type’ may be used uninitialized [-Wmaybe-uninitialized]
  112 |         if(best_p.type >= 0){
      |         ^~
Main.cpp:53:13: note: ‘best_p.main()::Pat::type’ was declared here
   53 |         Pat best_p;
      |             ^~~~~~

Judge Result