Submission #465955

#	Time	Username	Problem	Language	Result	Execution time	Memory
465955		nonsensenonsense1	Robots (APIO13_robots)	C++17	100 / 100	1006 ms	110040 KiB

robots

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <utility>

const int INF = 0x3f3f3f3f;

int move[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

inline void mnm(int &a, int b) 
{
	if (a > b) a = b;
}

const int N = 500;
const int M = 10;
int n, h, w;
std::pair<int, int> to[N][N][4];
int dist[M][M][N][N];
bool u[N][N];
char s[N][N + 1];

inline bool out(int x, int y) 
{
	return x >= h || x < 0 || y >= w || y < 0 || s[x][y] == 'x';
}

std::pair<int, int> to_f(int x, int y, int dir) 
{
	if (to[x][y][dir].second != -1) return to[x][y][dir];
	to[x][y][dir].second = 0;
	int dir_ = dir;
	if (s[x][y] == 'C') ++dir;
	else if (s[x][y] == 'A') --dir;
	if (dir == 4) dir = 0;
	if (dir == -1) dir = 3;
	if (out(x + move[dir][0], y + move[dir][1])) to[x][y][dir_] = std::make_pair(x, y);
	else to[x][y][dir_] = to_f(x + move[dir][0], y + move[dir][1], dir);
	return to[x][y][dir_];
}

int main() 
{
	memset(dist, 0x3f, N * N * M * M << 2);
	scanf("%d%d%d", &n, &w, &h);
	for (int i = 0; i < h; ++i) {
		scanf("%s", s[i]);
		for (int j = 0; j < w; ++j) {
			if (s[i][j] >= '1' && s[i][j] <= '9') dist[s[i][j] - '1'][s[i][j] - '1'][i][j] = 0;
			for (int k = 0; k < 4; ++k) to[i][j][k] = std::make_pair(-1, -1);
		}
	}
	for (int d = 0; d < n; ++d) for (int l = 0; l < n - d; ++l) {
		int r = l + d;
		std::vector<std::pair<int, std::pair<int, int> > > pos;
		int (*ptr)[N] = dist[l][r];
		for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) if (ptr[i][j] != INF) pos.push_back(std::make_pair(ptr[i][j], std::make_pair(i, j)));
		std::sort(pos.begin(), pos.end());
		if (d == n - 1 && !pos.empty()) {
			printf("%d\n", pos.front().first);
			return 0;
		}
		std::queue<std::pair<int, int> > q;
		memset(u, 0, N * N);
		for (int i = 0; i < (int)pos.size() || !q.empty();) {
			int x, y;
			if (q.empty() || i < (int)pos.size() && pos[i].first <= ptr[q.front().first][q.front().second]) {
				x = pos[i].second.first;
				y = pos[i].second.second;
				++i;
			}
			else {
				x = q.front().first;
				y = q.front().second;
				q.pop();
			}
			if (!u[x][y]) {
				u[x][y] = true;
				for (int j = 0; j < l; ++j) mnm(dist[j][r][x][y], dist[j][l - 1][x][y] + ptr[x][y]);
				for (int j = r + 1; j < n; ++j) mnm(dist[l][j][x][y], dist[r + 1][j][x][y] + ptr[x][y]);
				for (int j = 0; j < 4; ++j) {
					std::pair<int, int> next = to_f(x, y, j);
					if (next.second != -1) {
						mnm(ptr[next.first][next.second], ptr[x][y] + 1);
						q.push(next);
					}
				}
			}
		}
	}
	printf("-1\n");
	return 0;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:68:41: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   68 |    if (q.empty() || i < (int)pos.size() && pos[i].first <= ptr[q.front().first][q.front().second]) {
      |                     ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d%d%d", &n, &w, &h);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%s", s[i]);
      |   ~~~~~^~~~~~~~~~~~

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