# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
858980 |
2023-10-09T13:55:51 Z |
12345678 |
Robots (APIO13_robots) |
C++17 |
|
4 ms |
2652 KB |
#include <bits/stdc++.h>
using namespace std;
const int nx=505;
int n, w, h, dpa[nx][nx], dpb[nx][nx], dx[]={1, 0, -1, 0}, dy[]={0, 1, 0, -1}, ans=INT_MAX;
char mp[nx][nx];
pair<int, int> s1, s2;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>w>>h;
for (int i=1; i<=h; i++)
{
for (int j=1; j<=w; j++)
{
cin>>mp[i][j];
if (mp[i][j]=='1') s1={i, j};
if (mp[i][j]=='2') s2={i, j};
}
}
queue<pair<int, int>> q;
for (int i=1; i<=h; i++) for (int j=1; j<=w; j++) dpa[i][j]=dpb[i][j]=INT_MAX;
dpa[s1.first][s1.second]=0;
q.push(s1);
while (!q.empty())
{
auto [x, y]=q.front();
q.pop();
for (int i=0; i<4; i++)
{
int tx=x, ty=y, d=i;
while (1)
{
if (mp[tx][ty]=='A') d=(d+1)%4;
if (mp[tx][ty]=='C') d=(d-1+4)%4;
tx=tx+dx[d];
ty=ty+dy[d];
if ((tx<1||tx>h||ty<1||ty>w)||mp[tx][ty]=='x')
{
tx=tx-dx[d];
ty=ty-dy[d];
if (dpa[tx][ty]>dpa[x][y]+1) dpa[tx][ty]=dpa[x][y]+1, q.push({tx, ty});
break;
}
}
}
}
dpb[s2.first][s2.second]=0;
q.push(s2);
while (!q.empty())
{
auto [x, y]=q.front();
q.pop();
for (int i=0; i<4; i++)
{
int tx=x, ty=y, d=i;
while (1)
{
if (mp[tx][ty]=='A') d=(d+1)%4;
if (mp[tx][ty]=='C') d=(d-1+4)%4;
tx=tx+dx[d];
ty=ty+dy[d];
if ((tx<1||tx>h||ty<1||ty>w)||mp[tx][ty]=='x')
{
tx=tx-dx[d];
ty=ty-dy[d];
if (dpb[tx][ty]>dpb[x][y]+1) dpb[tx][ty]=dpb[x][y]+1, q.push({tx, ty});
break;
}
}
}
}
for (int i=1; i<=h; i++) for (int j=1; j<=w; j++) if (dpa[i][j]!=INT_MAX&&dpb[i][j]!=INT_MAX) ans=min(ans, dpa[i][j]+dpb[i][j]);
cout<<((ans==INT_MAX)?-1:ans);
}
/*
2 3 3
1.x
.x.
x.2*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2404 KB |
Output is correct |
3 |
Correct |
0 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
0 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2404 KB |
Output is correct |
3 |
Correct |
0 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
0 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
0 ms |
2396 KB |
Output is correct |
8 |
Correct |
0 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
0 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2404 KB |
Output is correct |
3 |
Correct |
0 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
0 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
0 ms |
2396 KB |
Output is correct |
8 |
Correct |
0 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
0 ms |
2396 KB |
Output is correct |
11 |
Incorrect |
4 ms |
2652 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2404 KB |
Output is correct |
3 |
Correct |
0 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
0 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
0 ms |
2396 KB |
Output is correct |
8 |
Correct |
0 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
0 ms |
2396 KB |
Output is correct |
11 |
Incorrect |
4 ms |
2652 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |