Submission #288067

#TimeUsernameProblemLanguageResultExecution timeMemory
288067NamnamseoRobots (APIO13_robots)C++17
0 / 100
100 ms163844 KiB
#include <cstdio> #include <cstring> #include <utility> #include <functional> #include <queue> #define rep(i,n) for(int i=0;i<n;++i) #define rrep(i,n) for(int i=1;i<=n;++i) #define x first #define y second #define eb emplace_back using namespace std; using pp=pair<int,int>; int n, m, k; char q[510][510]; pp e[510][510][4]; pp il[10]; using t4=tuple<int,int,int,int>; int dp[510][510][50]; const int dx[5] = {0, 1, 0, -1}, *dy = dx+1; pp E(int x, int y, int d) { pp &ret = e[x][y][d]; if (ret.x) return ret; int nx=x+dx[d], ny=y+dy[d]; if (1<=nx && nx<=n && 1<=ny && ny<=m && q[nx][ny]!='x') { switch(q[nx][ny]) { case 'A': ret = E(nx, ny, (d+3)%4); break; case 'C': ret = E(nx, ny, (d+1)%4); break; default: ret = E(nx, ny, d); break; } return ret; } else return ret={x, y}; } int C[10][10]; queue<t4> Q[500*500+1]; int main() { scanf("%d%d%d",&k,&m,&n); rrep(i, n) { scanf("%s", q[i]+1); rrep(j, m) if ((q[i][j]&48)==48) il[q[i][j]-48]={i,j}; } { static int p = 0; rrep(i, k) rrep(j, i) C[j][i] = ++p; } memset(dp,0x3f,sizeof(dp)); rrep(i, k) { dp[il[i].x][il[i].y][C[i][i]] = 0; Q[0].emplace(il[i].x, il[i].y, i, i); } const int inf = 0x3f3f3f3f; rrep(len, k) { rrep(i, n) rrep(j, m) rrep(l, k-len+1) { int r = l+len-1; int p = C[l][r]; for(int t=l; t<r; ++t) { int v = dp[i][j][C[l][t]]+ dp[i][j][C[t+1][r]]; if (v < dp[i][j][p]) { dp[i][j][p] = v; } } if (dp[i][j][p] != inf) { Q[dp[i][j][p]].emplace(i, j, l, r); } } for(int ans=0; ans<n*m; ++ans) while (Q[ans].size()) { int x,y,l,r; tie(x,y,l,r) = Q[ans].front(); Q[ans].pop(); int p = C[l][r]; if (dp[x][y][p] != ans) continue; rep(d, 4) { pp t = E(x, y, d); if (t == pp(x, y)) continue; if (dp[t.x][t.y][p] > dp[x][y][p]+1) { dp[t.x][t.y][p] = dp[x][y][p]+1; Q[dp[t.x][t.y][p]].emplace(t.x, t.y, l, r); } } } } int ans = inf; rrep(i, n) rrep(j, m) ans = min(ans, dp[i][j][C[1][k]]); if (ans == inf) ans = -1; printf("%d\n", ans); return 0; }

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |  scanf("%d%d%d",&k,&m,&n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
robots.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |   scanf("%s", q[i]+1);
      |   ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...