Submission #364696

#	Time	Username	Problem	Language	Result	Execution time	Memory
364696		Nima_Naderi	Robots (APIO13_robots)	C++14	100 / 100	1140 ms	126556 KiB

robots

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
 
const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int N=505;
 
int n, m, k, u, v, x, y, t, a, b, ans;
char A[N][N];
pii nex[4][N][N];
bool mark[4][N][N];
int dp[10][10][N][N];
bool inq[N][N];
int DX[]={0, +1, 0, -1}, DY[]={+1, 0, -1, 0};
pii tof[N*N*10];
 
pii go(int dir, int x, int y){
//	cerr<<"go "<<dir<<"  "<<x<<", "<<y<<endl;
	if (nex[dir][x][y]!=pii(0, 0)) return nex[dir][x][y];
	if (mark[dir][x][y]) return nex[dir][x][y]={-1, -1};
	mark[dir][x][y]=1;
	int dd=dir;
	if (A[x][y]=='A') dd=(dir+3)%4;
	if (A[x][y]=='C') dd=(dir+1)%4;
	int xx=x+DX[dd], yy=y+DY[dd];
	if (!xx || xx>n || !yy || yy>m || A[xx][yy]=='x') return nex[dir][x][y]={x, y};
	return nex[dir][x][y]=go(dd, xx, yy);
}
 
inline void upd(int& x, int y){ x=min(x, y);}
 
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>k>>m>>n;
	for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin>>A[i][j];
	for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) if (A[i][j]!='x')
		for (int d:{0, 1, 2, 3}) go(d, i, j);
	// hope nex is right
	
	memset(dp, 63, sizeof(dp));
	for (int l=k; l; l--) for (int r=l; r<=k; r++){
		for (int x=1; x<=n; x++) for (int y=1; y<=m; y++){
			if (l<r){
				for (int i=l; i<r; i++) upd(dp[l][r][x][y], dp[l][i][x][y]+dp[i+1][r][x][y]);
			}
			else if (A[x][y]=='0'+l) upd(dp[l][r][x][y], 0);
		}
		// BFS or spfa or whatever
		int tail=0, head=0;
		for (int x=1; x<=n; x++) for (int y=1; y<=m; y++) if (dp[l][r][x][y]<inf) tof[head++]={x, y};
		sort(tof, tof+head, [&](pii i, pii j){
			return dp[l][r][i.first][i.second]<dp[l][r][j.first][j.second];	
		});
		while (tail<head){
			int x=tof[tail].first, y=tof[tail].second;
			tail++;
			inq[x][y]=0;
			for (int d:{0, 1, 2, 3}) if (nex[d][x][y]!=pii(-1, -1)){
				int xx=nex[d][x][y].first, yy=nex[d][x][y].second;
				if (dp[l][r][x][y]+1<dp[l][r][xx][yy]){
					dp[l][r][xx][yy]=dp[l][r][x][y]+1;
					if (!inq[xx][yy]){
//						Q.push({xx, yy});
						tof[head++]={xx, yy};
						inq[xx][yy]=1;
					}
				}
			}
		}
	}
	ans=inf;
	for (int x=1; x<=n; x++) for (int y=1; y<=m; y++) upd(ans, dp[1][k][x][y]);
	if (ans>=inf) ans=-1;
	cout<<ans<<'\n';
	
	return 0;
}
/*
2 2 2
x1
2x
 
*/

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