Submission #221976

#	Time	Username	Problem	Language	Result	Execution time	Memory
221976		Bruteforceman	Robots (APIO13_robots)	C++11	100 / 100	1058 ms	146680 KiB

robots

#include "bits/stdc++.h"
using namespace std;
using pii = pair <int, int>;
const int dx[] = {0, -1, 0, 1};
const int dy[] = {1, 0, -1, 0};
pii dp[4][505][505];
bool vis[4][505][505];
char s[505][505];
int N, n, m;
int opt[10][10][505][505];
const int inf = 1e9;
vector <pii> can[10 * 505 * 505];

struct data {
    int x, y, cost;
    data (int x, int y, int cost) : x(x), y(y), cost(cost) {}
    data () {}
    bool operator < (data d) const {
        return cost > d.cost;
    }
};
bool inside(int x, int y) {
	return (0 <= x && x < n) && (0 <= y && y < m);
}
pii func(int d, int x, int y) {
	if(vis[d][x][y] == true) return dp[d][x][y];
	vis[d][x][y] = true;
    int nd = d;
    if(s[x][y] == 'A') nd = (d + 1) % 4;
	if(s[x][y] == 'C') nd = (d + 3) % 4; 
	int nx = x + dx[nd];
	int ny = y + dy[nd];
	if(inside(nx, ny) && s[nx][ny] != 'x') {
		dp[d][x][y] = func(nd, nx, ny);
	} else {
		dp[d][x][y] = pii(x, y);
	}
	return dp[d][x][y];
}

void propagate(int l, int r) {
    int maxDist = N * n * m;
    for(int i = 0; i <= maxDist; i++) {
        can[i].clear();
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(opt[l][r][i][j] <= maxDist) can[opt[l][r][i][j]].emplace_back(i, j);
        }
    }
    for(int i = 0; i < maxDist; i++) {
        for(auto p : can[i]) {
            if(opt[l][r][p.first][p.second] < i) continue;
            for(int d = 0; d < 4; d++) {
                pii q = func(d, p.first, p.second);
                if(q.first == -1) continue;
                int &ret = opt[l][r][q.first][q.second];
                if(ret > i + 1) {
                    ret = i + 1;
                    can[ret].emplace_back(q);
                }
            }
        }
    }
    return ;
}
int main(int argc, char const *argv[])
{
	scanf("%d %d %d", &N, &n, &m);
    swap(n, m);
    for(int i = 0; i < n; i++) {
        scanf("%s", s[i]);
    }
    for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			for(int d = 0; d < 4; d++) {
				dp[d][i][j] = pii(-1, -1);
				vis[d][i][j] = false;
			}
		}
	}
    for(int i = 1; i <= N; i++) {
        for(int j = i; j <= N; j++) {
            for(int x = 0; x < n; x++) {
                for(int y = 0; y < m; y++) {
                    opt[i][j][x][y] = inf;
                }
            }
        }
    }
    for(int x = 0; x < n; x++) {
        for(int y = 0; y < m; y++) {
            if(isdigit(s[x][y])) {
                int c = s[x][y] - '0';
                opt[c][c][x][y] = 0;
                propagate(c, c);
            }
        }
    }
    for(int sz = 2; sz <= N; sz++) {
        for(int i = 1; i <= N - sz + 1; i++) {
            int j = i + sz - 1; 
            for(int x = 0; x < n; x++) {
                for(int y = 0; y < m; y++) {
                    for(int k = i; k < j; k++) {
                        opt[i][j][x][y] = min(opt[i][j][x][y], opt[i][k][x][y] + opt[k + 1][j][x][y]);
                    }
                }
            }
            propagate(i, j);
        }
    }
    int ans = inf;
    for(int x = 0; x < n; x++) for(int y = 0; y < m; y++) ans = min(ans, opt[1][N][x][y]);
    if(ans == inf) ans = -1;
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

robots.cpp: In function 'int main(int, const char**)':
robots.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &N, &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", s[i]);
         ~~~~~^~~~~~~~~~~~

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