Submission #369437

# Submission time Handle Problem Language Result Execution time Memory
369437 2021-02-21T16:50:12 Z YJU Robots (APIO13_robots) C++14
0 / 100
97 ms 163844 KB
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long 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<<60);
#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[10][10][N][N],dis[N][N][2][5];
//dp[l][r][x][y] 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;
char grid[N][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);
	//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)REP1(j,C){
		while((grid[i][j]=getchar())=='\n');
		//cin>>grid[i][j];
	}
	//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++){
			//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{
					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]);
					}
				}
				//
				dis[i][j][0][0]=dp[l][r][i][j];
				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)
						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)
						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(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(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));
						}
					}
				}
			}
			//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...
*/
# Verdict Execution time Memory Grader output
1 Runtime error 97 ms 163844 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 97 ms 163844 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 97 ms 163844 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 97 ms 163844 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -