| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 218015 |
2020-03-31T12:25:39 Z |
SamAnd |
Robots (APIO13_robots) |
C++17 |
|
274 ms |
163840 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 502, K = 9, INF = 1000000009;
const int xx[4] = {-1, 0, 1, 0};
const int yy[4] = {0, 1, 0, -1};
struct ban
{
int x, y;
ban(){}
ban(int x, int y)
{
this->x = x;
this->y = y;
}
};
int n, m, k;
char a[N][N];
int sx[K], sy[K];
int c[N][N][4];
ban u[N][N][4];
void dfs(int x, int y, int z)
{
c[x][y][z] = 1;
int hx = x + xx[z];
int hy = y + yy[z];
int hz = z;
if (!(hx >= 1 && hx <= n && hy >= 1 && hy <= m) || a[hx][hy] == 'x')
{
hx = x;
hy = y;
}
else if (a[hx][hy] == 'C')
hz = (z + 1) % 4;
else if (a[hx][hy] == 'A')
hz = (z - 1 + 4) % 4;
if (hx == x && hy == y)
{
u[x][y][z] = ban(x, y);
c[x][y][z] = 2;
return;
}
if (!c[hx][hy][hz])
{
dfs(hx, hy, hz);
u[x][y][z] = u[hx][hy][hz];
c[x][y][z] = 2;
return;
}
if (c[hx][hy][hz] == 2)
{
u[x][y][z] = u[hx][hy][hz];
c[x][y][z] = 2;
return;
}
u[x][y][z] = ban(-1, -1);
c[x][y][z] = 2;
return;
}
int**** dp;
bool cc[N][N];
vector<ban> q[N * N * K];
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d%d%d", &k, &m, &n);
for (int i = 1; i <= n; ++i)
scanf(" %s", (a[i] + 1));
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
if ('1' <= a[i][j] && a[i][j] <= '9')
{
sx[a[i][j] - '1'] = i;
sy[a[i][j] - '1'] = j;
a[i][j] = '.';
}
}
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
for (int k = 0; k < 4; ++k)
{
if (!c[i][j][k])
{
dfs(i, j, k);
}
}
}
}
//printf("PRRRRR\n");
dp = new int***[K];
for (int i = 0; i < K; ++i)
{
dp[i] = new int**[K - i];
for (int j = 0; j <= K - i; ++j)
{
dp[i][j] = new int*[N];
for (int x = 0; x < N; ++x)
{
dp[i][j][x] = new int[N];
for (int y = 0; y < N; ++y)
dp[i][j][x][y] = INF;
}
}
}
for (int d = 0; d < k; ++d)
{
for (int l = 0; l <= k - d; ++l)
{
if (d == 0)
dp[l][d][sx[l]][sy[l]] = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
for (int m = 0; m < d; ++m)
dp[l][d][i][j] = min(dp[l][d][i][j], dp[l][m][i][j] + dp[l + m + 1][d - m - 1][i][j]);
}
}
memset(cc, false, sizeof cc);
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
if (dp[l][d][i][j] != INF)
q[dp[l][d][i][j]].push_back(ban(i, j));
}
}
for (int ii = 0; ii < N * N * K; ++ii)
{
while (!q[ii].empty())
{
ban t = q[ii].back();
q[ii].pop_back();
if (cc[t.x][t.y])
continue;
cc[t.x][t.y] = true;
for (int i = 0; i < 4; ++i)
{
ban h = u[t.x][t.y][i];
if (h.x == -1)
continue;
if (dp[l][d][t.x][t.y] + 1 < dp[l][d][h.x][h.y])
{
dp[l][d][h.x][h.y] = dp[l][d][t.x][t.y] + 1;
q[dp[l][d][h.x][h.y]].push_back(h);
}
}
}
}
}
}
int ans = INF;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
ans = min(ans, dp[0][k - 1][i][j]);
}
}
if (ans == INF)
printf("-1\n");
else
printf("%d\n", ans);
return 0;
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &k, &m, &n);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", (a[i] + 1));
~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
107512 KB |
Output is correct |
| 2 |
Correct |
93 ms |
107512 KB |
Output is correct |
| 3 |
Correct |
92 ms |
107512 KB |
Output is correct |
| 4 |
Correct |
93 ms |
107640 KB |
Output is correct |
| 5 |
Correct |
93 ms |
107640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
107512 KB |
Output is correct |
| 2 |
Correct |
93 ms |
107512 KB |
Output is correct |
| 3 |
Correct |
92 ms |
107512 KB |
Output is correct |
| 4 |
Correct |
93 ms |
107640 KB |
Output is correct |
| 5 |
Correct |
93 ms |
107640 KB |
Output is correct |
| 6 |
Correct |
96 ms |
107512 KB |
Output is correct |
| 7 |
Correct |
94 ms |
107576 KB |
Output is correct |
| 8 |
Correct |
96 ms |
107512 KB |
Output is correct |
| 9 |
Correct |
95 ms |
107512 KB |
Output is correct |
| 10 |
Correct |
99 ms |
107640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
107512 KB |
Output is correct |
| 2 |
Correct |
93 ms |
107512 KB |
Output is correct |
| 3 |
Correct |
92 ms |
107512 KB |
Output is correct |
| 4 |
Correct |
93 ms |
107640 KB |
Output is correct |
| 5 |
Correct |
93 ms |
107640 KB |
Output is correct |
| 6 |
Correct |
96 ms |
107512 KB |
Output is correct |
| 7 |
Correct |
94 ms |
107576 KB |
Output is correct |
| 8 |
Correct |
96 ms |
107512 KB |
Output is correct |
| 9 |
Correct |
95 ms |
107512 KB |
Output is correct |
| 10 |
Correct |
99 ms |
107640 KB |
Output is correct |
| 11 |
Runtime error |
274 ms |
163840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
107512 KB |
Output is correct |
| 2 |
Correct |
93 ms |
107512 KB |
Output is correct |
| 3 |
Correct |
92 ms |
107512 KB |
Output is correct |
| 4 |
Correct |
93 ms |
107640 KB |
Output is correct |
| 5 |
Correct |
93 ms |
107640 KB |
Output is correct |
| 6 |
Correct |
96 ms |
107512 KB |
Output is correct |
| 7 |
Correct |
94 ms |
107576 KB |
Output is correct |
| 8 |
Correct |
96 ms |
107512 KB |
Output is correct |
| 9 |
Correct |
95 ms |
107512 KB |
Output is correct |
| 10 |
Correct |
99 ms |
107640 KB |
Output is correct |
| 11 |
Runtime error |
274 ms |
163840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
