| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 217985 |
2020-03-31T11:36:18 Z |
SamAnd |
Robots (APIO13_robots) |
C++17 |
|
261 ms |
81272 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 303, K = 11, 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[K][K][N][N];
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] - '0'] = i;
sy[a[i][j] - '0'] = j;
a[i][j] = '.';
}
}
}
for (int i0 = 0; i0 < K; ++i0)
for (int i1 = 0; i1 < K; ++i1)
for (int i2 = 0; i2 < N; ++i2)
for (int i3 = 0; i3 < N; ++i3)
dp[i0][i1][i2][i3] = INF;
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);
}
}
}
}
for (int d = 1; d <= k; ++d)
{
for (int l = 1; l <= k - d + 1; ++l)
{
int r = l + d - 1;
if (l == r)
dp[l][r][sx[l]][sy[l]] = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
for (int m = l; m < r; ++m)
dp[l][r][i][j] = min(dp[l][r][i][j], dp[l][m][i][j] + dp[m + 1][r][i][j]);
}
}
memset(cc, false, sizeof cc);
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
if (dp[l][r][i][j] != INF)
q[dp[l][r][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][r][t.x][t.y] + 1 < dp[l][r][h.x][h.y])
{
dp[l][r][h.x][h.y] = dp[l][r][t.x][t.y] + 1;
q[dp[l][r][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[1][k][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 |
51 ms |
67576 KB |
Output is correct |
| 2 |
Correct |
50 ms |
67576 KB |
Output is correct |
| 3 |
Correct |
49 ms |
67576 KB |
Output is correct |
| 4 |
Correct |
50 ms |
67704 KB |
Output is correct |
| 5 |
Correct |
50 ms |
67704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
67576 KB |
Output is correct |
| 2 |
Correct |
50 ms |
67576 KB |
Output is correct |
| 3 |
Correct |
49 ms |
67576 KB |
Output is correct |
| 4 |
Correct |
50 ms |
67704 KB |
Output is correct |
| 5 |
Correct |
50 ms |
67704 KB |
Output is correct |
| 6 |
Correct |
50 ms |
67576 KB |
Output is correct |
| 7 |
Correct |
50 ms |
67704 KB |
Output is correct |
| 8 |
Correct |
50 ms |
67576 KB |
Output is correct |
| 9 |
Correct |
49 ms |
67576 KB |
Output is correct |
| 10 |
Correct |
49 ms |
67704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
67576 KB |
Output is correct |
| 2 |
Correct |
50 ms |
67576 KB |
Output is correct |
| 3 |
Correct |
49 ms |
67576 KB |
Output is correct |
| 4 |
Correct |
50 ms |
67704 KB |
Output is correct |
| 5 |
Correct |
50 ms |
67704 KB |
Output is correct |
| 6 |
Correct |
50 ms |
67576 KB |
Output is correct |
| 7 |
Correct |
50 ms |
67704 KB |
Output is correct |
| 8 |
Correct |
50 ms |
67576 KB |
Output is correct |
| 9 |
Correct |
49 ms |
67576 KB |
Output is correct |
| 10 |
Correct |
49 ms |
67704 KB |
Output is correct |
| 11 |
Correct |
191 ms |
76024 KB |
Output is correct |
| 12 |
Correct |
54 ms |
72568 KB |
Output is correct |
| 13 |
Correct |
121 ms |
72056 KB |
Output is correct |
| 14 |
Correct |
261 ms |
81272 KB |
Output is correct |
| 15 |
Correct |
174 ms |
73208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
67576 KB |
Output is correct |
| 2 |
Correct |
50 ms |
67576 KB |
Output is correct |
| 3 |
Correct |
49 ms |
67576 KB |
Output is correct |
| 4 |
Correct |
50 ms |
67704 KB |
Output is correct |
| 5 |
Correct |
50 ms |
67704 KB |
Output is correct |
| 6 |
Correct |
50 ms |
67576 KB |
Output is correct |
| 7 |
Correct |
50 ms |
67704 KB |
Output is correct |
| 8 |
Correct |
50 ms |
67576 KB |
Output is correct |
| 9 |
Correct |
49 ms |
67576 KB |
Output is correct |
| 10 |
Correct |
49 ms |
67704 KB |
Output is correct |
| 11 |
Correct |
191 ms |
76024 KB |
Output is correct |
| 12 |
Correct |
54 ms |
72568 KB |
Output is correct |
| 13 |
Correct |
121 ms |
72056 KB |
Output is correct |
| 14 |
Correct |
261 ms |
81272 KB |
Output is correct |
| 15 |
Correct |
174 ms |
73208 KB |
Output is correct |
| 16 |
Execution timed out |
17 ms |
24320 KB |
Time limit exceeded (wall clock) |
| 17 |
Halted |
0 ms |
0 KB |
- |
