| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 252108 |
2020-07-24T08:27:58 Z |
T0p_ |
Robots (APIO13_robots) |
C++14 |
|
91 ms |
163844 KB |
#include<bits/stdc++.h>
using namespace std;
struct DJK
{
int i;
int j;
int s;
long long w;
bool operator < (const DJK & o) const{
return w > o.w;
}
};
int n, m;
int di[4] = {-1, 0, 1, 0}, dj[4] = {0, 1, 0, -1};
long long dis[505][505][515];
pair<int, int> des[4][505][505];
char t[505][505];
queue<pair<int, int>> bfs;
priority_queue<DJK> djk;
bool visit[505][505][515];
pair<int, int> compute(int i, int j, int d)
{
if(des[d][i][j].first) return des[d][i][j];
int dd = d;
if(t[i][j] == 'A')
{
dd += 3;
dd %= 4;
}
else if(t[i][j] == 'C')
{
dd += 5;
dd %= 4;
}
int ii = i + di[dd], jj = j + dj[dd];
if(ii < 1 || jj < 1 || ii > n || jj > m || t[ii][jj] == 'x') return des[d][i][j] = {i, j};
return des[d][i][j] = compute(ii, jj, dd);
}
int main()
{
int K;
scanf(" %d %d %d",&K,&m,&n);
for(int i=1 ; i<=n ; i++)
scanf(" %s",t[i]+1);
for(int i=1 ; i<=n ; i++)
for(int j=1 ; j<=m ; j++)
{
for(int k=1 ; k<(1<<K) ; k++) dis[i][j][k] = 1e9;
if(t[i][j] == 'x') continue ;
if('1' <= t[i][j] && t[i][j] <= '9')
{
int s = 1<<(t[i][j]-'0'-1);
dis[i][j][s] = 0;
djk.push({i, j, s, 0});
}
for(int k=0 ; k<4 ; k++)
compute(i, j, k);
}
while(!djk.empty())
{
int i = djk.top().i;
int j = djk.top().j;
int s = djk.top().s;
long long w = djk.top().w;
djk.pop();
if(visit[i][j][s]) continue ;
visit[i][j][s] = true;
if(s+1 == (1<<K))
{
printf("%d\n",w);
return 0;
}
for(int k=0 ; k<4 ; k++)
{
int ii = des[k][i][j].first, jj = des[k][i][j].second;
for(int it=0 ; it<(1<<K) ; it++)
{
int ss = it|s;
if(dis[ii][jj][it] != 1e9 && dis[ii][jj][ss] > dis[ii][jj][it] + w + 1)
{
dis[ii][jj][ss] = dis[ii][jj][it] + w + 1;
djk.push({ii, jj, ss, dis[ii][jj][ss]});
}
}
}
}
printf("-1\n");
return 0;
}
/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:74:19: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
printf("%d\n",w);
^
robots.cpp:46:7: 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:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s",t[i]+1);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1024 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
512 KB |
Output is correct |
| 9 |
Correct |
0 ms |
512 KB |
Output is correct |
| 10 |
Correct |
1 ms |
896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1024 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
512 KB |
Output is correct |
| 9 |
Correct |
0 ms |
512 KB |
Output is correct |
| 10 |
Correct |
1 ms |
896 KB |
Output is correct |
| 11 |
Runtime error |
91 ms |
163844 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1024 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
512 KB |
Output is correct |
| 9 |
Correct |
0 ms |
512 KB |
Output is correct |
| 10 |
Correct |
1 ms |
896 KB |
Output is correct |
| 11 |
Runtime error |
91 ms |
163844 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
