Submission #1261916

#TimeUsernameProblemLanguageResultExecution timeMemory
1261916k12_khoiRobots (APIO13_robots)C++17
0 / 100
0 ms320 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<int,int> #define X first #define Y second const int N=505; const int K=12; const int oo=1e9+1; int n,m,k,dist,l,r,u,v,x,y,SAVE_L,SAVE_R,d[K][K][N][N]; int dx[]={1,0,0,-1},dy[]={0,1,-1,0}; int A[]={1,3,0,2},C[]={2,0,3,1}; pii nxt[N][N][5]; bool visited[N][N][5]; char s[N][N]; vector <pii> ve; deque <pii> dq; pii dfs(int u,int v,int dir) { if (s[u][v]=='A') dir=A[dir]; if (s[u][v]=='C') dir=C[dir]; if (nxt[u][v][dir]!=make_pair(0,0)) return nxt[u][v][dir]; if (visited[u][v][dir]) return nxt[u][v][dir]=make_pair(-1,-1); visited[u][v][dir]=true; if (s[u+dx[dir]][v+dy[dir]]=='x') return nxt[u][v][dir]=make_pair(u,v); return nxt[u][v][dir]=dfs(u+dx[dir],v+dy[dir],dir); } bool cmp(pii a,pii b) { return d[SAVE_L][SAVE_R][a.X][a.Y]>d[SAVE_L][SAVE_R][b.X][b.Y]; } int dial() { for (int l=k;l>=1;l--) for (int r=l;r<=n;r++) { ve.clear(); for (int x=1;x<=n;x++) for (int y=1;y<=m;y++) if (d[l][r][x][y]!=oo) ve.push_back(make_pair(x,y)); SAVE_L=l; SAVE_R=r; sort(ve.begin(),ve.end(),cmp); if (!ve.empty() and l==1 and r==k) return d[l][r][ve.back().X][ve.back().Y]; while (!dq.empty() or !ve.empty()) { if (dq.empty()) { dq.push_back(ve.back()); ve.pop_back(); } while (!dq.empty()) { u=dq.front().X; v=dq.front().Y; dq.pop_front(); dist=d[l][r][u][v]; while (!ve.empty() and d[l][r][ve.back().X][ve.back().Y]==dist) { dq.push_front(ve.back()); ve.pop_back(); } for (int i=l-1;i>=1;i--) d[i][r][u][v]=min(d[i][r][u][v],d[l][r][u][v]+d[i][l-1][u][v]); for (int j=r+1;j<=k;j++) d[l][j][u][v]=min(d[l][j][u][v],d[l][r][u][v]+d[r+1][j][u][v]); for (int dir=0;dir<=3;dir++) if (nxt[u][v][dir]!=make_pair(-1,-1)) { x=nxt[u][v][dir].X; y=nxt[u][v][dir].Y; if (d[l][r][x][y]>dist+1) { d[l][r][x][y]=dist+1; dq.push_back(make_pair(x,y)); } } } } } return -1; } int main() { ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL); cin >> k >> m >> n; for (int i=0;i<=n+1;i++) s[i][0]=s[i][m+1]='x'; for (int j=0;j<=m+1;j++) s[0][j]=s[n+1][j]='x'; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) cin >> s[i][j]; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) for (int dir=0;dir<=3;dir++) if (s[i][j]!='x') dfs(i,j,dir); for (int l=1;l<=k;l++) for (int r=l;r<=k;r++) for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) d[l][r][i][j]=oo; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (s[i][j]>'0' and s[i][j]<=k+'0') { int id=s[i][j]-'0'; d[id][id][i][j]=0; } cout << dial(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...