Submission #1093954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093954		Trisanu_Das	Robots (APIO13_robots)	C++17	100 / 100	936 ms	57536 KiB

robots

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;
 
const int inf = 1e9, N = 505;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
 
int n, w, h, dt[9][9][N][N];
char ipt[N][N];
 
bool vis[N][N][4], solved[9][9];
 
 
pii ini[9], nxt[N][N][4];
queue<pii>q;
 
vector<pair<int,pii> > vec;
 
bool valid (int A, int B) {
	if(A < 1 || A > h) return false;
	if(B < 1 || B > w) return false;
	if(ipt[A][B] == 'x') return false;
	return true;
}
 
void calc(int A, int B, int i) {
	if(vis[A][B][i]) return;
	vis[A][B][i] = true;
	int nA = A+dx[i], nB = B+dy[i];
	if(!valid(nA,nB)) {
		nxt[A][B][i] = {A,B};
		return;
	}
	if(ipt[nA][nB]=='C') {
		calc(nA, nB, (i+1)%4);
		nxt[A][B][i] = nxt[nA][nB][(i+1)%4];
	}
	else if(ipt[nA][nB]=='A') {
		calc(nA, nB, (i+3)%4);
		nxt[A][B][i] = nxt[nA][nB][(i+3)%4];
	}
	else {
		calc(nA, nB, i);
		nxt[A][B][i] = nxt[nA][nB][i];
	}
}
 
void solve(int S, int E) {
	if(solved[S][E]) return;
	solved[S][E] = true;
	for(int i=1;i<=h;i++) {
		for(int j=1;j<=w;j++) {
			dt[S][E][i][j] = inf;
		}
	}
	if(S == E) dt[S][E][ini[S].X][ini[S].Y] = 0;
	for(int k=S;k<E;k++) {
		solve(S,k);
		solve(k+1,E);
		for(int i=1;i<=h;i++) {
			for(int j=1;j<=w;j++) {
				dt[S][E][i][j] = min({inf, dt[S][E][i][j], dt[S][k][i][j] + dt[k+1][E][i][j]});
			}
		}
	}
	vec.clear();
	for(int i=1;i<=h;i++) {
		for(int j=1;j<=w;j++) {
			vec.push_back({dt[S][E][i][j], {i, j}});
		}
	}
	sort(vec.begin(),vec.end());
	for(int k=0;k<vec.size();k++) {
		if(dt[S][E][vec[k].Y.X][vec[k].Y.Y] < vec[k].X) continue;
		q.push(vec[k].Y);
		while(!q.empty()) {
			int A, B;
			tie(A, B) = q.front();
			q.pop();
			for(int i=0;i<4;i++) {
				int nA, nB;
				tie(nA, nB) = nxt[A][B][i];
				if(dt[S][E][A][B] + 1 < dt[S][E][nA][nB]) {
					dt[S][E][nA][nB] = dt[S][E][A][B] + 1;
					q.push({nA, nB});
				}
			}
		}
	}
}
 
int main()
{
	scanf("%d%d%d",&n,&w,&h);
	for(int i=1;i<=h;i++) {
		scanf("%s",ipt[i]+1);
		for(int j=1;j<=w;j++) {
			if('1' <= ipt[i][j] && ipt[i][j] <= '9') {
				ini[ipt[i][j]-'1'] = {i, j};
			}
		}
	}
	for(int i=1;i<=h;i++) {
		for(int j=1;j<=w;j++) {
			for(int k=0;k<4;k++) {
				calc(i,j,k);
			}
		}
	}
	solve(0,n-1);
	int ans = inf;
	for(int i=1;i<=h;i++) {
		for(int j=1;j<=w;j++) {
			ans = min(ans, dt[0][n-1][i][j]);
		}
	}
	printf("%d\n", ans == inf ? -1 : ans);
}

Compilation message (stderr)

robots.cpp: In function 'void solve(int, int)':
robots.cpp:76:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int k=0;k<vec.size();k++) {
      |              ~^~~~~~~~~~~
robots.cpp: In function 'int main()':
robots.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |  scanf("%d%d%d",&n,&w,&h);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
robots.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |   scanf("%s",ipt[i]+1);
      |   ~~~~~^~~~~~~~~~~~~~~

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