Submission #124202

#	Time	Username	Problem	Language	Result	Execution time	Memory
124202		youngyojun	Robots (APIO13_robots)	C++11	100 / 100	528 ms	101184 KiB

robots

#include <bits/stdc++.h>
#define eb emplace_back
#define INF (0x3f3f3f3f)
using namespace std;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
inline void fuk() { puts("-1"); exit(0); }

int D[9][9][505][505];

int PY[505][505][4], PX[505][505][4];
char A[505][505];

int N, H, W, Ans = INF;

vector<int> EV[505*505];
void spread(int D[][505]) {
	int mn = INF;
	for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++)
		if(D[i][j] < mn) mn = D[i][j];
	if(INF <= mn) fuk();
	for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++)
		if(D[i][j] <= mn + H*W)
			EV[D[i][j]-mn].eb(i<<10|j);
	for(int l = 0; l <= H*W; l++) {
		auto &V = EV[l];
		for(int key : V) {
			int i = key>>10, j = key&((1<<10)-1);
			for(int dr = 0, ni, nj; dr < 4; dr++) {
				ni = PY[i][j][dr]; nj = PX[i][j][dr];
				if(ni < 1 || nj < 1 || H < ni || W < nj) continue;
				if(D[ni][nj] <= mn+l+1) continue;
				D[ni][nj] = mn+l+1;
				EV[l+1].eb(ni<<10|nj);
			}
		}
		V.clear();
	}
}

void f(int y, int x, int dr) {
	int ndr = dr;
	if('A' == A[y][x]) ndr++;
	if('C' == A[y][x]) ndr--;
	if(ndr < 0) ndr = 3; if(3 < ndr) ndr = 0;
	PY[y][x][dr] = PX[y][x][dr] = -1;
	int ny = y+dy[ndr], nx = x+dx[ndr];
	if(!ny || !nx || H < ny || W < nx || 'x' == A[ny][nx]) {
		PY[y][x][dr] = y;
		PX[y][x][dr] = x;
		return;
	}
	if(!PY[ny][nx][ndr]) f(ny, nx, ndr);
	PY[y][x][dr] = PY[ny][nx][ndr];
	PX[y][x][dr] = PX[ny][nx][ndr];
}

int main() {
	scanf("%d%d%d", &N, &W, &H);
	for(int i = 1; i <= H; i++) scanf(" %s", A[i]+1);
	for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++) if('x' != A[i][j])
		for(int dr = 0; dr < 4; dr++) if(!PY[i][j][dr]) f(i, j, dr);
	fill(D[0][0][0], D[8][8][504]+505, INF);
	for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++) if('1' <= A[i][j] && A[i][j] <= '9') {
		int c = (A[i][j]&15) - 1;
		D[c][c][i][j] = 0;
	}
	for(int i = 0; i < N; i++) spread(D[i][i]);
	for(int l = 1; l < N; l++) {
		for(int s = 0, e = l; e < N; s++, e++) {
			for(int k = s; k < e; k++) {
				for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++) {
					int t = D[s][k][i][j] + D[k+1][e][i][j];
					if(t < D[s][e][i][j]) D[s][e][i][j] = t;
				}
			}
			spread(D[s][e]);
		}
	}
	for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++)
		if(D[0][N-1][i][j] < Ans) Ans = D[0][N-1][i][j];
	cout << (INF <= Ans ? -1 : Ans) << endl;
	return 0;
}

Compilation message (stderr)

robots.cpp: In function 'void f(int, int, int)':
robots.cpp:44:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ndr < 0) ndr = 3; if(3 < ndr) ndr = 0;
  ^~
robots.cpp:44:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ndr < 0) ndr = 3; if(3 < ndr) ndr = 0;
                       ^~
robots.cpp: In function 'int main()':
robots.cpp:58: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:59:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= H; i++) scanf(" %s", A[i]+1);
                              ~~~~~^~~~~~~~~~~~~~~

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