| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 369471 |
2021-02-21T18:01:59 Z |
YJU |
로봇 (APIO13_robots) |
C++14 |
|
1500 ms |
56748 KB |
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=5e2+5;
const ld pi=acos(-1);
const ll INF=(1LL<<29);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
struct node{
ll Dis,x,y,ty,dir;
node(ll _a,ll _b,ll _c,ll _d,ll _e):Dis(_a),x(_b),y(_c),ty(_d),dir(_e){};
//state :at (x,y) ty(turn yet?0:1) dir(direction)
// 3
// |
//4-0-2
// |
// 1
void out(){
cout<<"Dis("<<Dis<<"),x("<<x<<"),y("<<y<<"),ty("<<ty<<"),dir("<<dir<<")\n";
}
};
struct cmp{
bool operator()(node A,node B){
return A.Dis>B.Dis;
}
};
priority_queue<node,vector<node>,cmp> pq;
ll dp[N][N][11][11],dis[N][N][2][5],nxtx[N][N][5],nxty[N][N][5];
//dp[x][y][l][r] represents minimum times of operation to make robot[l,r] stay at grid[x][y]
ll dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1};
ll n,R,C;
string grid[N];
bool invalid(ll x,ll y){
return !(0<x&&x<=R&&0<y&&y<=C&&grid[x][y]!='x');
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
//input
cin>>n>>C>>R;
REP1(i,R)cin>>grid[i],grid[i]="x"+grid[i];
//input end
//prepare
REP1(i,R)REP1(j,C){
nxtx[i][j][3]=(invalid(i+dx[3],j)||grid[i+dx[3]][j]=='A'||grid[i+dx[3]][j]=='C'?i+dx[3]:nxtx[i+dx[3]][j][3]);
nxty[i][j][4]=(invalid(i,j+dy[4])||grid[i][j+dy[4]]=='A'||grid[i][j+dy[4]]=='C'?j+dy[4]:nxty[i][j+dy[4]][4]);
}
for(int i=R;i>=1;i--)for(int j=C;j>=1;j--){
nxtx[i][j][1]=(invalid(i+dx[1],j)||grid[i+dx[1]][j]=='A'||grid[i+dx[1]][j]=='C'?i+dx[1]:nxtx[i+dx[1]][j][1]);
nxty[i][j][2]=(invalid(i,j+dy[2])||grid[i][j+dy[2]]=='A'||grid[i][j+dy[2]]=='C'?j+dy[2]:nxty[i][j+dy[2]][2]);
nxtx[i][j][2]=nxtx[i][j][4]=i;
nxty[i][j][1]=nxty[i][j][3]=j;
}
//len = r-l+1 for robot[l,r]
for(int len=1;len<=n;len++){
for(int l=1,r=l+len-1;l+len-1<=n;l++,r++){
//merging robots to robot[l,r]
REP1(i,R)REP1(j,C){
REP(ty,2)REP(dir,5)dis[i][j][ty][dir]=INF;
if(len==1){
dp[i][j][l][r]=(grid[i][j]-'0'==l?0:INF);
}else{
dp[i][j][l][r]=INF;
for(int cut=l;cut+1<=r;cut++){
dp[i][j][l][r]=min(dp[i][j][l][r],dp[i][j][l][cut]+dp[i][j][cut+1][r]);
}
}
//
dis[i][j][0][0]=dp[i][j][l][r];
if(dis[i][j][0][0]<INF){
pq.push(node(dis[i][j][0][0],i,j,0,0));
}
//
}
//moving robots ( O(N*N*log(N*N) ) )
while(SZ(pq)){
node nd=pq.top();pq.pop();
if(nd.Dis!=dis[nd.x][nd.y][nd.ty][nd.dir])continue;
//nd.out();
if(nd.ty==0){
//have turned
if(nd.dir==0){
//stand at (nd.x,nd.y)
dp[nd.x][nd.y][l][r]=nd.Dis;
REP1(dir,4){
//push to dir (cost = 1)
if(dis[nd.x][nd.y][1][dir]>nd.Dis+1){
dis[nd.x][nd.y][1][dir]=nd.Dis+1;
pq.push(node(nd.Dis+1,nd.x,nd.y,1,dir));
}
}
}else{
//moving on or stop (cost = 0)
ll nx=nxtx[nd.x][nd.y][nd.dir],ny=nxty[nd.x][nd.y][nd.dir];
if(invalid(nx,ny)){
nx-=dx[nd.dir],ny-=dy[nd.dir];
if(dis[nx][ny][0][0]>nd.Dis){
dis[nx][ny][0][0]=nd.Dis;
pq.push(node(nd.Dis,nx,ny,0,0));
}
}else{
if(dis[nx][ny][1][nd.dir]>nd.Dis){
dis[nx][ny][1][nd.dir]=nd.Dis;
pq.push(node(nd.Dis,nx,ny,1,nd.dir));
}
}
}
}else if(nd.ty==1){
if(nd.dir==0)continue;
if(grid[nd.x][nd.y]=='A'){
ll ndir=(nd.dir+1==5?1:nd.dir+1);
if(dis[nd.x][nd.y][0][ndir]>nd.Dis){
dis[nd.x][nd.y][0][ndir]=nd.Dis;
pq.push(node(nd.Dis,nd.x,nd.y,0,ndir));
}
}else if(grid[nd.x][nd.y]=='C'){
ll ndir=(nd.dir-1==0?4:nd.dir-1);
if(dis[nd.x][nd.y][0][ndir]>nd.Dis){
dis[nd.x][nd.y][0][ndir]=nd.Dis;
pq.push(node(nd.Dis,nd.x,nd.y,0,ndir));
}
}else{
if(dis[nd.x][nd.y][0][nd.dir]>nd.Dis){
dis[nd.x][nd.y][0][nd.dir]=nd.Dis;
pq.push(node(nd.Dis,nd.x,nd.y,0,nd.dir));
}
}
}
}
}
}
ll ans=INF;
REP1(i,R)REP1(j,C){
ans=min(ans,dp[i][j][1][n]);
}
cout<<(ans==INF?-1:ans)<<"\n";
return 0;
}
/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
0 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
620 KB |
Output is correct |
| 5 |
Correct |
1 ms |
620 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
0 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
620 KB |
Output is correct |
| 5 |
Correct |
1 ms |
620 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
620 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
0 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
620 KB |
Output is correct |
| 5 |
Correct |
1 ms |
620 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
620 KB |
Output is correct |
| 11 |
Correct |
902 ms |
56748 KB |
Output is correct |
| 12 |
Correct |
45 ms |
53996 KB |
Output is correct |
| 13 |
Correct |
113 ms |
55148 KB |
Output is correct |
| 14 |
Execution timed out |
1595 ms |
55396 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
0 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
620 KB |
Output is correct |
| 5 |
Correct |
1 ms |
620 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
620 KB |
Output is correct |
| 11 |
Correct |
902 ms |
56748 KB |
Output is correct |
| 12 |
Correct |
45 ms |
53996 KB |
Output is correct |
| 13 |
Correct |
113 ms |
55148 KB |
Output is correct |
| 14 |
Execution timed out |
1595 ms |
55396 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
