| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 108990 |
2019-05-03T13:17:22 Z |
nxteru |
Robots (APIO13_robots) |
C++14 |
|
174 ms |
164864 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 2500000
struct t{
int r,y,x;
};
int h,w,n,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},m[505][505],dp[9][9][505][505],ans=INF;
vector<P>g[505][505];
stack<t>q[2500000];
void dfs(int y,int x,int d,int py,int px){
g[y][x].PB(P(py,px));
if(m[y][x]==2)d++;
if(m[y][x]==3)d+=3;
d%=4;
int ny=y+dy[d],nx=x+dx[d];
if(0<=ny&&ny<h&&0<=nx&&nx<w&&m[ny][nx]!=1)dfs(ny,nx,d,py,px);
}
int main(void){
scanf("%d%d%d",&n,&w,&h);
for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int y=0;y<h;y++)for(int x=0;x<w;x++)dp[i][j][y][x]=INF;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
char c;
scanf(" %c",&c);
if(c=='x')m[i][j]=1;
else if(c=='A')m[i][j]=2;
else if(c=='C')m[i][j]=3;
else if(c!='.'){
int p=c-'1';
dp[p][p][i][j]=0;
}
}
}
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(m[i][j]==1)continue;
for(int k=0;k<4;k++){
int ny=i+dy[k],nx=j+dx[k];
if(nx<0||nx>=w||ny<0||ny>=h||m[ny][nx]==1){
dfs(i,j,(k+2)%4,i,j);
}
}
}
}
for(int k=0;k+1<n;k++){
int mn=INF,mx=-1;
for(int l=0;l+k<n;l++){
int r=l+k;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
int d=dp[l][r][i][j];
if(d!=INF){
q[d].push(t{l,i,j});
mn=min(mn,d);
mx=max(mx,d);
}
}
}
}
queue<t>bfs;
while(mn<=mx||!bfs.empty()){
if(bfs.empty()){
while(!q[mn].empty()){
bfs.push(q[mn].top());
q[mn].pop();
}
mn++;
}
int r=bfs.front().r,y=bfs.front().y,x=bfs.front().x;
int c=dp[r][r+k][y][x];
bfs.pop();
if(mn<=mx&&c==mn){
while(!q[mn].empty()){
bfs.push(q[mn].top());
q[mn].pop();
}
mn++;
}
for(int i=0;i<g[y][x].size();i++){
int ny=g[y][x][i].F,nx=g[y][x][i].S;
if(dp[r][r+k][ny][nx]>c+1){
dp[r][r+k][ny][nx]=c+1;
bfs.push(t{r,ny,nx});
}
}
}
for(int l=0;l+k+1<n;l++){
int r=l+k+1;
for(int e=l;e<r;e++){
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
dp[l][r][i][j]=min(dp[l][r][i][j],dp[l][e][i][j]+dp[e+1][r][i][j]);
}
}
}
}
}
for(int i=0;i<h;i++)for(int j=0;j<w;j++)ans=min(ans,dp[0][n-1][i][j]);
if(ans==INF)ans=-1;
printf("%d\n",ans);
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:86:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[y][x].size();i++){
~^~~~~~~~~~~~~~~
robots.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&n,&w,&h);
~~~~~^~~~~~~~~~~~~~~~~~~
robots.cpp:31:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c",&c);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
174 ms |
164864 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
174 ms |
164864 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
174 ms |
164864 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
174 ms |
164864 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
