Submission #49332

#	Time	Username	Problem	Language	Result	Execution time	Memory
49332		hamzqq9	Robots (APIO13_robots)	C++14	100 / 100	551 ms	109372 KiB

robots

#include<bits/stdc++.h>
#define lf double
#define ll long long
#define cc pair<char,char>
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000000
#define inf 1000000000
#define N 505
#define LOG 20
#define magic 100
#define KOK 250
#define EPS 0.0025
#define pw(x) (1<<(x))
#define PI 3.1415926535
using namespace std;

int ans=inf,n,w,h,tot;
int dp[50][N][N],tut[10][10];
ii go[N][N][4],place[10];
bool gov[N][N][4],vis[50][N][N];
int way[4][2]={1,0,0,-1,-1,0,0,1};
char a[N][N];
vector<ii> sh[N*N];

void sp(int state) {

	int mn=inf;

	for(int i=1;i<=h;i++) {

		for(int j=1;j<=w;j++) {

			if(dp[state][i][j]==inf) continue ;

			if(dp[state][i][j]<mn) mn=dp[state][i][j];

			sh[dp[state][i][j]].pb({i,j});

		}

	}

	for(int i=mn;i<N*N;i++) {

		while(sz(sh[i])) {

			ii pl=sh[i].back();

			sh[i].ppb();

			if(vis[state][pl.st][pl.nd]) continue ;

			vis[state][pl.st][pl.nd]=1;

			dp[state][pl.st][pl.nd]=i;

			for(int j=0;j<4;j++) {

				ii to=go[pl.st][pl.nd][j];

				if(vis[state][to.st][to.nd]) continue ;

				sh[i+1].pb(to);

			}

		}

	}

}

ii dfs(int x,int y,int dir) {

	if(gov[x][y][dir]) return go[x][y][dir];

	gov[x][y][dir]=1;

	int todir=dir;

	if(a[x][y]=='A') todir=(dir-1+4)%4;
	else if(a[x][y]=='C') todir=(dir+1)%4;

	int tox=x+way[todir][0];
	int toy=y+way[todir][1];

	if(a[tox][toy]=='x' || tox==0 || toy==0 || tox>h || toy>w) return go[x][y][dir]={x,y};

	return go[x][y][dir]=dfs(tox,toy,todir);

}

int main() {

//	freopen("input.txt","r",stdin);

	scanf("%d %d %d",&n,&w,&h);

	for(int i=1;i<=n;i++) {

		for(int s=1;s<=n-i+1;s++) {

			tut[s][s+i-1]=++tot;

		}

	} 

	for(int i=0;i<50;i++) {

		for(int j=0;j<N;j++) {

			for(int k=0;k<N;k++) {

				dp[i][j][k]=inf;

			}

		}

	}

	for(int i=1;i<=h;i++) {

		scanf("%s",a[i]+1);

		for(int j=1;j<=w;j++) {

			if(a[i][j]>='1' && a[i][j]<='9') {

				dp[tut[a[i][j]-'0'][a[i][j]-'0']][i][j]=0;
				place[a[i][j]-'0']={i,j};
				a[i][j]='.';

			}

		}

	}

	for(int i=1;i<=h;i++) {

		for(int j=1;j<=w;j++) {

			if(a[i][j]=='x') continue ;

			for(int dir=0;dir<4;dir++) {

				if(!gov[i][j][dir]) {

					dfs(i,j,dir);

				}

			}

		}

	}

	for(int i=1;i<=n;i++) {

		sp(tut[i][i]);

	}

	for(int l=2;l<=n;l++) {

		for(int s=1;s<=n-l+1;s++) {

			int now=tut[s][s+l-1];

			int e=s+l-1;

			for(int e1=s;e1<e;e1++) {

				int now1=tut[s][e1];
				int now2=tut[e1+1][e];

				for(int i=1;i<=h;i++) {

					for(int j=1;j<=w;j++) {

						dp[now][i][j]=min(dp[now][i][j],dp[now1][i][j]+dp[now2][i][j]);

					}

				}

			}

			sp(now);

		}

	}

	for(int i=1;i<=h;i++) {

		for(int j=1;j<=w;j++) {

			ans=min(ans,dp[tut[1][n]][i][j]);

			//printf("%d %d %d\n",i,j,dp[tut[1][n]][i][j]);

		}

	}

	if(ans==inf) ans=-1;

	printf("%d",ans);
  
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:120:7: 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:148:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",a[i]+1);
   ~~~~~^~~~~~~~~~~~~

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