제출 #578614

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
578614		MohammadAghil	로봇 (APIO13_robots)	C++17	60 / 100	397 ms	163840 KiB

robots

      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
    using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
    #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
      #define per(i,r,l) for(int i = (r); i >= (l); i--)
        #define rep(i,l,r) for(int i = (l); i < (r); i++)
           #define all(x) x.begin(), x.end()
              #define sz(x) (int)(x).size()
                  #define pb push_back
                      #define ss second
                           #define ff first
                                   void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 5e2 + 1, lg = 9, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}
 
int st[maxn][maxn], n, m, k;
pp ply[lg], adj[maxn][maxn][4];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool vis[maxn][maxn][4];
int dist[lg][lg][maxn][maxn];
 
pp dfs(int x, int y, int dir){
     if(vis[x][y][dir]) return adj[x][y][dir];
     adj[x][y][dir] = {-1, -1};
     vis[x][y][dir] = true;
     int d = dir;
     if(st[x][y] == 2) d = (d + 3)%4;
     if(st[x][y] == 3) d = (d + 1)%4;
     int i = x + dx[d], j = y + dy[d];
     if(i < 0 || i == n || j < 0 || j == m || !st[i][j]) return adj[x][y][dir] = {x, y};
     return adj[x][y][dir] = dfs(i, j, d);
}
 
int main(){
     cin.tie(0) -> sync_with_stdio(0);
     cin >> k >> m >> n;
     rep(i,0,n) rep(j,0,m){
          char c; cin >> c;
          if(c == '.') st[i][j] = 1;
          if(c == 'A') st[i][j] = 2;
          if(c == 'C') st[i][j] = 3;
          if(c >= '0' && c <= '9') st[i][j] = 1, ply[c-'1'] = {i, j};
     }
     rep(i,0,n) rep(j,0,m) rep(d,0,4) dfs(i, j, d);
 
     rep(i,0,lg) rep(j,0,lg) rep(t,0,n) rep(f,0,m) dist[i][j][t][f] = inf;
 
     rep(t,0,k){
          deque<pp> q{ply[t]}; dist[t][t][ply[t].ff][ply[t].ss] = 0;
          while(sz(q)){
               auto[x, y] = q.front(); q.pop_front();
               rep(d,0,4) if(adj[x][y][d].ff + 1 && dist[t][t][adj[x][y][d].ff][adj[x][y][d].ss] == inf){
                    q.push_back(adj[x][y][d]);
                    dist[t][t][adj[x][y][d].ff][adj[x][y][d].ss] = dist[t][t][x][y] + 1;
               }
          }
     }
 
     vector<vector<pp>> pos(lg*n*m + 1);
     rep(l,2,k+1){
          rep(i,0,k-l+1){
               int j = i + l - 1;
               // priority_queue<pair<int, pp>, vector<pair<int, pp>>, greater<pair<int, pp>>> q;
               rep(x,0,n) rep(y,0,m){
                    rep(m,i,j){
                         dist[i][j][x][y] = min(dist[i][j][x][y], dist[i][m][x][y] + dist[m+1][j][x][y]);
                    }
                    if(dist[i][j][x][y] - inf) pos[dist[i][j][x][y]].pb({x, y});
                    dist[i][j][x][y] = inf;
               }
 
               // while(sz(q)){
               //      auto[w, t] = q.top(); q.pop();
               //      auto[x, y] = t;
               //      if(w - dist[i][j][x][y]) continue;
               //      rep(d,0,4){
               //           auto[xp, yp] = adj[x][y][d];
               //           if(xp + 1 && dist[i][j][xp][yp] > w + 1){
               //                q.push({dist[i][j][xp][yp] = w + 1, {xp, yp}});
               //           }
               //      }
               // }
 
               rep(s,0,sz(pos)){
                    for(auto[x, y]: pos[s]) if(dist[i][j][x][y] == inf){
                         dist[i][j][x][y] = s;
                         rep(d,0,4) if(adj[x][y][d].ff + 1 && dist[i][j][adj[x][y][d].ff][adj[x][y][d].ss] == inf){
                              pos[s + 1].pb(adj[x][y][d]);
                         }
                    }
                    pos[s].clear();
               }
          }
     }
 
     int ans = inf;
     rep(i,0,n) rep(j,0,m) ans = min(ans, dist[0][k-1][i][j]);
     cout << (ans == inf? -1: ans) << '\n';
     return 0; 
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40