Submission #15939

#	Time	Username	Problem	Language	Result	Execution time	Memory
15939		myungwoo	Robots (APIO13_robots)	C++14	100 / 100	931 ms	112896 KiB

robots

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mt make_tuple
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()

int yy[]={-1, 0, 1, 0}, xx[]={0, 1, 0, -1};
int R, N, M;
int D[10][10][501][501];
int Y[501][501][4], X[501][501][4];
bool needless[501][501][4], V[501][501][4];
char A[501][502];

bool dfs(int y, int x, int d)
{
	if (V[y][x][d]){
		if (!Y[y][x][d]) needless[y][x][d] = 1;
		return needless[y][x][d];
	}
	V[y][x][d] = 1;
	int nd = d;
	if (A[y][x] == 'A') nd = (d+3)%4;
	if (A[y][x] == 'C') nd = (d+1)%4;
	int ny = y+yy[nd], nx = x+xx[nd];
	if (ny < 1 || nx < 1 || ny > N || nx > M || A[ny][nx] == 'x'){
		Y[y][x][d] = y; X[y][x][d] = x;
		return 0;
	}
	dfs(ny, nx, nd);
	if (needless[ny][nx][nd]) needless[y][x][d] = 1;
	Y[y][x][d] = Y[ny][nx][nd], X[y][x][d] = X[ny][nx][nd];
	return needless[y][x][d];
}

void bfs(int dst[501][501])
{
	vector <tuple<int, int, int>> arr;
	for (int i=1;i<=N;i++) for (int j=1;j<=M;j++) if (dst[i][j] < 1e9){
		arr.pb(mt(dst[i][j], i, j));
	}
	if (arr.empty()) return;
	sort(all(arr));
	int pnt = 1;
	queue <int> que;
	que.push(get<1>(arr[0])); que.push(get<2>(arr[0]));
	while (!que.empty()){
		int y = que.front(); que.pop();
		int x = que.front(); que.pop();
		while (pnt < sz(arr) && dst[y][x]+1 >= get<0>(arr[pnt])){
			int ty = get<1>(arr[pnt]), tx = get<2>(arr[pnt]);
			if (dst[ty][tx] == get<0>(arr[pnt]))
				que.push(ty), que.push(tx);
			pnt++;
		}
		for (int d=0;d<4;d++){
			if (dfs(y, x, d)) continue;
			int ny = Y[y][x][d], nx = X[y][x][d];
			if (dst[ny][nx] > dst[y][x]+1)
				dst[ny][nx] = dst[y][x]+1, que.push(ny), que.push(nx);
		}
	}
}

int main()
{
	scanf("%d%d%d", &R, &M, &N);
	for (int i=1;i<=N;i++) scanf("%s", A[i]+1);
	for (int i=1;i<=R;i++){
		for (int j=1;j<=N;j++) for (int k=1;k<=M;k++){
			D[i][i][j][k] = (A[j][k]-'0' == i) ? 0 : 1e9;
		}
		bfs(D[i][i]);
	}
	for (int l=2;l<=R;l++){
		for (int s=1;s<=R-l+1;s++){
			int e = s+l-1;
			for (int y=1;y<=N;y++) for (int x=1;x<=M;x++){
				D[s][e][y][x] = 1e9;
				for (int k=s;k<e;k++){
					D[s][e][y][x] = min(D[s][e][y][x], D[s][k][y][x] + D[k+1][e][y][x]);
				}
			}
			bfs(D[s][e]);
		}
	}
	int ans = 1e9;
	for (int i=1;i<=N;i++) for (int j=1;j<=M;j++){
		ans = min(ans, D[1][R][i][j]);
	}
	printf("%d\n", ans < 1e9 ? ans : -1);
}

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