Submission #369451

#	Time	Username	Problem	Language	Result	Execution time	Memory
369451		YJU	Robots (APIO13_robots)	C++14	30 / 100	1575 ms	17160 KiB

robots

#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+25;
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;
	}
};

deque<node> pq;
//priority_queue<node,vector<node>,cmp> pq;


ll dp[12][12][N][N],dis[N][N][3][6];
//dp[l][r][x][y] represents minimum times of operation to make robot[l,r] stay at grid[x][y]

ll dx[6]={0,1,0,-1,0},dy[6]={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');
}

void AAA(ll l,ll r){
	while(SZ(pq)){
		node nd=pq.front();pq.pop_front();
		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){
				dp[l][r][nd.x][nd.y]=min(dp[l][r][nd.x][nd.y],nd.Dis);
				//stand at (nd.x,nd.y)
				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.pb(node(nd.Dis+1,nd.x,nd.y,1,dir));
					}
				}
			}else{
				//moving on or stop (cost = 0)
				if(invalid(nd.x+dx[nd.dir],nd.y+dy[nd.dir])){
					if(dis[nd.x][nd.y][0][0]>nd.Dis){
						dis[nd.x][nd.y][0][0]=nd.Dis;
						pq.push_front(node(nd.Dis,nd.x,nd.y,0,0));
					}
				}else{
					ll nx=nd.x+dx[nd.dir],ny=nd.y+dy[nd.dir];
					if(dis[nx][ny][1][nd.dir]>nd.Dis){
						dis[nx][ny][1][nd.dir]=nd.Dis;
						pq.push_front(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_front(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_front(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_front(node(nd.Dis,nd.x,nd.y,0,nd.dir));
				}
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	//prepare
	//REP(ii,10)REP(jj,10)REP(i,N)REP(j,N)dp[ii][jj][i][j]=INF;
	//prepare end
	
	//input
	cin>>n>>C>>R;
	REP1(i,R)cin>>grid[i],grid[i]="x"+grid[i];
	//input end
	
	//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++){
			vector<node> lis;
			//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[l][r][i][j]=(grid[i][j]-'0'==l?0:INF);
				}else{
					dp[l][r][i][j]=INF;
					for(int cut=l;cut+1<=r;cut++){
						dp[l][r][i][j]=min(dp[l][r][i][j],dp[l][cut][i][j]+dp[cut+1][r][i][j]);
					}
				}
				//
				if(dp[l][r][i][j]<INF){
					lis.pb(node(dp[l][r][i][j],i,j,0,0));
				}
				//
			}
			sort(lis.begin(),lis.end(),[](node A,node B){
				return A.Dis<B.Dis;	
			});
			//moving robots ( O(N*N) )
			for(node i:lis){
				if(dis[i.x][i.y][0][0]>i.Dis){
					dis[i.x][i.y][0][0]=i.Dis;
					pq.pb(i);
					AAA(l,r);
				}
			}
			//update after moving
			
			//cout<<"robot["<<l<<","<<r<<"]\n";
			/*REP1(i,R)REP1(j,C){
				dp[l][r][i][j]=min(dp[l][r][i][j],dis[i][j][0][0]);
				//cout<<setw(2)<<(dp[l][r][i][j]==INF?-1:dp[l][r][i][j])<<(j==C?"\n":" ");
			}*/
		}
	}
	ll ans=INF;
	REP1(i,R)REP1(j,C){
		ans=min(ans,dp[1][n][i][j]);
	}
	cout<<(ans==INF?-1:ans)<<"\n";
	return 0;
}
/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/

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