Submission #109002

#	Time	Username	Problem	Language	Result	Execution time	Memory
109002		nxteru	Robots (APIO13_robots)	C++14	30 / 100	226 ms	115880 KiB

robots

#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 22500000
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[45][505][505],ans=INF,sf[9][9];
vector<P>g[505][505];
vector<t>q[810000];
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);
    int mxs=0;
    for(int i=0;i<n;i++)for(int j=i;j<n;j++)sf[i][j]=mxs++;
    for(int i=0;i<mxs;i++)for(int y=0;y<h;y++)for(int x=0;x<w;x++)dp[i][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[sf[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[sf[l][r]][i][j];
					if(d!=INF){
						q[d].PB(t{l,i,j});
						mn=min(mn,d);
						mx=max(mx,d);
					}
				}
			}
		}
		queue<t>bfs;
		while(mn<=mx||!bfs.empty()){
			if(bfs.empty()){
				for(int i=0;i<q[mn].size();i++)bfs.push(q[mn][i]);
				q[mn].clear();
				mn++;
			}
			int r=bfs.front().r,y=bfs.front().y,x=bfs.front().x;
			int c=dp[sf[r][r+k]][y][x];
			bfs.pop();
			if(mn<=mx&&c==mn){
				for(int i=0;i<q[mn].size();i++)bfs.push(q[mn][i]);
				q[mn].clear();
				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[sf[r][r+k]][ny][nx]>c+1){
					dp[sf[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[sf[l][r]][i][j]=min(dp[sf[l][r]][i][j],dp[sf[l][e]][i][j]+dp[sf[e+1][r]][i][j]);
					}
				}
			}
		}
	}
	for(int i=0;i<h;i++)for(int j=0;j<w;j++)ans=min(ans,dp[sf[0][n-1]][i][j]);
	if(ans==INF)ans=-1;
	printf("%d\n",ans);
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:72:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<q[mn].size();i++)bfs.push(q[mn][i]);
                 ~^~~~~~~~~~~~~
robots.cpp:80:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<q[mn].size();i++)bfs.push(q[mn][i]);
                 ~^~~~~~~~~~~~~
robots.cpp:84: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:33:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c",&c);
    ~~~~~^~~~~~~~~~

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