| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 23603 |
2017-05-15T11:37:52 Z |
gs14004 |
Robots (APIO13_robots) |
C++11 |
|
1500 ms |
111960 KB |
#include <bits/stdc++.h>
using namespace std;
struct Pos{ int x, y; };
struct Dat{
Pos p; int d;
bool operator<(const Dat &oth) const { return d < oth.d; }
};
const int inf = 1e9, dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int n, h, w, x[10], y[10], md[502][502][10][10], c[10][10], s[502][502], ans = inf;
char b[502][502];
Pos dp[502][502][4];
vector<Dat> v;
queue<Pos> q;
int get(int a, int b, int c, int d){
if(a > c) swap(a, c);
if(b > d) swap(b, d);
return s[c][d] - s[a - 1][d] - s[c][b - 1] + s[a - 1][b - 1];
}
int av(const Pos &p){ return (p.x > 0) && (p.y > 0) && (p.x <= h) && (p.y <= w) && (b[p.x][p.y] != 'x'); }
Pos wh(Pos p, int d){
if(dp[p.x][p.y][d].x != 0) return dp[p.x][p.y][d];
int s = 1, e = max(w, h);
while(s <= e){
int m = (s + e) / 2;
int nx = p.x + dx[d] * m, ny = p.y + dy[d] * m;
if(!av({nx, ny}) || get(p.x + dx[d], p.y + dy[d], nx, ny)) e = m - 1;
else s = m + 1;
}
int nx = p.x + dx[d] * s, ny = p.y + dy[d] * s;
if(!av({nx, ny})){
nx -= dx[d]; ny -= dy[d];
dp[p.x][p.y][d] = {nx, ny};
}
else{
dp[p.x][p.y][d] = wh({nx, ny}, (d + b[nx][ny] - 'A' + 1) % 4);
}
return dp[p.x][p.y][d];
}
void dnc(int s, int e){
if(c[s][e]) return;
c[s][e] = 1;
for(int k = s; k < e; k++){
dnc(s, k); dnc(k + 1, e);
for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++){
md[i][j][s][e] = min(md[i][j][s][e], md[i][j][s][k] + md[i][j][k + 1][e]);
}
}
}
v.clear();
for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++) if(md[i][j][s][e] < inf) v.push_back({{i, j}, md[i][j][s][e]});
sort(v.begin(), v.end());
for(auto &cur : v){
if(cur.d != md[cur.p.x][cur.p.y][s][e]) continue;
q.push(cur.p);
while(!q.empty()){
Pos cp = q.front(); q.pop();
int nd = md[cp.x][cp.y][s][e] + 1;
for(int i = 0; i < 4; i++){
Pos np = wh(cp, i);
if(md[np.x][np.y][s][e] > nd){
md[np.x][np.y][s][e] = nd;
q.push(np);
}
}
}
}
}
int main(){
scanf("%d%d%d", &n, &w, &h);
for(int i = 1; i <= h; i++){
scanf("%s", b[i] + 1);
for(int j = 1; j <= w; j++){
if('1' <= b[i][j] && b[i][j] <= '9'){
x[b[i][j] - '0'] = i;
y[b[i][j] - '0'] = j;
}
else if(b[i][j] != '.') s[i][j]++;
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
}
for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++) for(int k = 1; k <= n; k++) for(int l = k; l <= n; l++)
md[i][j][k][l] = inf;
for(int i = 1; i <= n; i++){
md[x[i]][y[i]][i][i] = 0;
}
dnc(1, n);
for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++) ans = min(ans, md[i][j][1][n]);
printf("%d\n", ans == inf ? -1 : ans);
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:77:29: 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:79:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", b[i] + 1);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 2 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 3 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 4 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 5 |
Correct |
0 ms |
109572 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 2 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 3 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 4 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 5 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 6 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 7 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 8 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 9 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 10 |
Correct |
0 ms |
109572 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 2 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 3 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 4 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 5 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 6 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 7 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 8 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 9 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 10 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 11 |
Correct |
336 ms |
110232 KB |
Output is correct |
| 12 |
Correct |
23 ms |
109572 KB |
Output is correct |
| 13 |
Correct |
103 ms |
109572 KB |
Output is correct |
| 14 |
Correct |
579 ms |
110808 KB |
Output is correct |
| 15 |
Correct |
266 ms |
109940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 2 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 3 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 4 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 5 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 6 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 7 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 8 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 9 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 10 |
Correct |
0 ms |
109572 KB |
Output is correct |
| 11 |
Correct |
336 ms |
110232 KB |
Output is correct |
| 12 |
Correct |
23 ms |
109572 KB |
Output is correct |
| 13 |
Correct |
103 ms |
109572 KB |
Output is correct |
| 14 |
Correct |
579 ms |
110808 KB |
Output is correct |
| 15 |
Correct |
266 ms |
109940 KB |
Output is correct |
| 16 |
Correct |
1016 ms |
109572 KB |
Output is correct |
| 17 |
Execution timed out |
1500 ms |
111960 KB |
Execution timed out |
| 18 |
Halted |
0 ms |
0 KB |
- |
