| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 42545 |
2018-02-28T04:03:34 Z |
funcsr |
Robots (APIO13_robots) |
C++14 |
|
1 ms |
128 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <queue>
#include <cstdio>
using namespace std;
typedef pair<int, int> P;
typedef pair<P, int> P2;
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define INF 1000001919
#define _1 first
#define _2 second
inline void chmin(int &x, int v) { if (x > v) x = v; }
const int DX[4] = {-1, 0, 1, 0};
const int DY[4] = {0, -1, 0, 1};
int N, W, H;
char A[500][500];
P dst[500][500][4];
int start;
/*
inline void tle_check() {
double passed = (double)(clock()-start) / (double)CLOCKS_PER_SEC;
if (passed>=1.0) {
//cout<<passed<<" passed\n";
abort();
}
}
*/
vector<P2> G[500][500][4];
//const int MAX_D = 10*500*500;
//const int MAX_D = 10*1000;
int X[9], Y[9];
int dp[9][9][500][500];
vector<P> Q[10*500*500];
bool used[500][500];
void bfs(int D[500][500]) {
rep(i, W) rep(j, H) used[i][j] = false;
int MAX_D = 0;
rep(x, W) rep(y, H) if (D[x][y] != INF) MAX_D = max(MAX_D, D[x][y]);
assert(MAX_D <= 500*500);
rep(x, W) rep(y, H) if (D[x][y] != INF) Q[D[x][y]].pb(P(x, y));
//rep(x, W) rep(y, H) if (D[x][y] != INF)cout<<"("<<x<<","<<y<<")->"<<D[x][y]<<"\n";
vector<P> q;
int r = 0;
while (true) {
if (r > MAX_D && q.empty()) break;
vector<P> nq;
if (r <= MAX_D) {
for (P p : Q[r]) {
int x = p._1, y = p._2;
if (!used[x][y]) {
used[x][y] = true;
q.pb(P(x, y));
}
}
}
for (P p : q) {
int x = p._1, y = p._2;
rep(k, 4) {
P np = dst[x][y][k];
if (np._1 != -1 && !used[np._1][np._2]) {
used[np._1][np._2] = true;
D[np._1][np._2] = r+1;
nq.pb(np);
}
}
}
q.clear();
swap(q, nq);
r++;
}
rep(i, MAX_D+1) Q[i].clear();
}
int main() {
start = clock();
scanf("%d %d %d", &N, &W, &H);
getchar();
rep(y, H) {
rep(x, W) {
A[x][y] = getchar();
if ('1' <= A[x][y] && A[x][y] <= '9') X[A[x][y]-'1'] = x, Y[A[x][y]-'1'] = y;
}
getchar();
}
rep(x, W) rep(y, H) rep(d, 4) dst[x][y][d] = P(-1, -1);
queue<P2> q;
rep(x, W) rep(y, H) if (A[x][y] != 'x') rep(d, 4) {
int nx = x+DX[d], ny = y+DY[d], nd = d;
if (nx<0||nx>=W||ny<0||ny>=H||A[nx][ny]=='x') {
dst[x][y][d] = P(x, y);
q.push(P2(P(x, y), d));
}
else {
if (A[nx][ny] == 'A') nd = (d+3)%4;
if (A[nx][ny] == 'C') nd = (d+1)%4;
G[nx][ny][nd].pb(P2(P(x, y), d));
}
}
while (!q.empty()) {
int x = q.front()._1._1, y = q.front()._1._2, d = q.front()._2;
q.pop();
for (P2 t : G[x][y][d]) {
assert(dst[t._1._1][t._1._2][t._2] == P(-1, -1));
dst[t._1._1][t._1._2][t._2] = dst[x][y][d];
q.push(t);
}
}
/*
rep(x, W) rep(y, H) if (A[x][y] != 'x') rep(d, 4) {
cout<<"dst["<<x<<","<<y<<","<<d<<"]="<<dst[x][y][d]._1<<","<<dst[x][y][d]._2<<"\n";
}
*/
rep(i, N) rep(j, N) rep(x, W) rep(y, H) dp[i][j][x][y] = INF;
rep(i, N) dp[i][i][X[i]][Y[i]] = 0;
for (int len=1; len<=N; len++) {
rep(l, N) {
int r = l+len-1;
if (r >= N) break;
rep(x, W) rep(y, H) for (int k=l; k<r; k++) chmin(dp[l][r][x][y], dp[l][k][x][y]+dp[k+1][r][x][y]);
bfs(dp[l][r]);
}
}
int m = INF;
rep(x, W) rep(y, H) chmin(m, dp[0][N-1][x][y]);
if (m == INF) m = -1;
printf("%d\n", m);
return 0;
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:82:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &N, &W, &H);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
128 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
128 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
128 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
128 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
