Submission #705758

#	Time	Username	Problem	Language	Result	Execution time	Memory
705758		hoangnghiep	Robots (APIO13_robots)	C++14	60 / 100	243 ms	163840 KiB

robots

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define repeat(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define p push
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define vii vector<vector<int>>
#define vi vector<int>
//#define DEBUG
//#define multipletest
using namespace std;
const int LIM=5e2;
const int mod=1e9+7;
const int maxn=20;
const int inf=1e9;
int n,m,x,y,t,num,e,q,w,h;
int dx[8]={-1,0,1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};
char c;
int dp[10][10][LIM+5][LIM+5];
vector<pii> memodfs[LIM+5][LIM+5];
bool vis[LIM+5][LIM+5];
vector<pii> dist[LIM*LIM+5];
char grid[LIM+5][LIM+5];
bool check(int x,int y){
    if(x<=0 || x>n || y<=0 || y>m || grid[x][y]=='x'){
   return false;
     }
    return true;
}
pii dfs(int i,int j,int k){
	while(true){
	    if(grid[i][j]=='C'){
	    	k=(k+1)%4;
		}
		else if(grid[i][j]=='A'){
			k=(k+3)%4;
		}
		int x=i+dx[k];
		int y=j+dy[k];
		if(check(x,y)==false) return {i,j};
		i=x,j=y;
	}
}
void bfs(int l,int r){
	   // cout<<"bfs "<<l<<" "<<r<<endl;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			vis[i][j]=false;
		}
	}
	for(int i=0;i<=n*m+5;++i){
		dist[i].clear();
	}
	int mn=inf;
	int mx=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(dp[l][r][i][j]!=-1){
				dist[dp[l][r][i][j]].push_back({i,j});
				mn=min(mn,dp[l][r][i][j]);
				mx=max(mx,dp[l][r][i][j]);
			}
		}
	}
	for(int i=0;i<=n*m+5;++i){
		for(auto tmp:dist[i]){
			int x=tmp.f;
			int y=tmp.s;
			if(vis[x][y]) continue;
			vis[x][y]=1;
			for(auto nxt:memodfs[x][y]){
				int nx=nxt.f;
				int ny=nxt.s;
				if((dp[l][r][nx][ny]>dp[l][r][x][y]+1) || dp[l][r][nx][ny]==-1){
					dp[l][r][nx][ny]=dp[l][r][x][y]+1;
					dist[dp[l][r][nx][ny]].push_back({nx,ny});
				}
			}
		}
	}
}
void solve(){
//Sieve();
//   precal();
    #ifdef interactive
    testcase();
    #endif
    cin>>num>>m>>n;
    for(int i=0;i<10;++i){
    	for(int j=0;j<10;++j){
    		for(int k=1;k<=n;++k){
    			for(int l=1;l<=m;++l){
    				dp[i][j][k][l]=-1;
				}
			}
		}
	}
    for(int i=1;i<=n;++i){
    	for(int j=1;j<=m;++j){
    		cin>>grid[i][j];
    		if('0'<=grid[i][j] && grid[i][j]<='9'){
    			 x=grid[i][j]-'0';
    			dp[x][x][i][j]=0;
			}
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			for(int k=0;k<4;++k){
				memodfs[i][j].push_back(dfs(i,j,k));
			}
		}
	}
	for(int d=0;d<num;++d){
		for(int l=1;l+d<=num;++l){
			int r=l+d;
			for(int mid=l;mid<r;++mid){
				for(int i=1;i<=n;++i){
					for(int j=1;j<=m;++j){
						if((dp[l][r][i][j]==-1 || dp[l][r][i][j]>dp[l][mid][i][j]+dp[mid+1][r][i][j]) 
						&& (dp[l][mid][i][j]!=-1 && dp[mid+1][r][i][j]!=-1)){
							dp[l][r][i][j]=dp[l][mid][i][j] + dp[mid+1][r][i][j];
						}
					}
				}
			}
			bfs(l,r);
		}
	}
	int ans=inf;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
		if(dp[1][num][i][j]!=-1)	ans = min(ans,dp[1][num][i][j]);
		}
	}
	if(ans==inf) cout<<-1<<endl;
	else cout<<ans<<endl;
}
signed main(){
  // freopen(".inp","r",stdin);
  // freopen(".out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int test;
	test=1;
	#ifdef multipletest
	cin>>test;
	#endif
	while(test--){
        solve();
        #ifdef DEBUG
		cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
	    #endif
	}
}

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