| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 498354 |
2021-12-25T04:50:17 Z |
mansur |
Robots (APIO13_robots) |
C++17 |
|
0 ms |
320 KB |
#include<bits/stdc++.h>
/*
#pragma optimize ("g",on)
#pragma GCC optimize ("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
*/
//01001101 01100001 01101011 01101000 01100001 01100111 01100001 01111001
using namespace std;
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ll long long
#define pb push_back
#define sz(a) a.size()
#define nl '\n'
#define popb pop_back()
#define ld double
#define ull unsigned long long
#define ff first
#define ss second
#define fix fixed << setprecision
#define pii pair<int, int>
#define E exit (0)
#define int long long
const int inf = 1e15, N = 3e5 + 5, mod = 998244353;
vector<pii> dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int d1[301][301], d2[301][301];
char c[301][301];
int n, m;
map<pii, int> was1[4], was2[4];
pii dfs1(pii pos, int d, int dst) {
if (c[pos.ff][pos.ss] == 'A') d = (d + 1) % 4;
if (c[pos.ff][pos.ss] == 'C') d = (d + 3) % 4;
if (was1[d][pos] <= dst) {
return {-1, -1};
}
was1[d][pos] = dst;
pii p = pos;
p.ff += dir[d].ff;
p.ss += dir[d].ss;
if (p.ff > n || p.ss > m || p.ff < 1 || p.ss < 1 || c[p.ff][p.ss] == 'x') {
d1[pos.ff][pos.ss] = min(d1[pos.ff][pos.ss], dst);
return pos;
}
return dfs1(p, d, dst);
}
pii dfs2(pii pos, int d, int dst) {
if (c[pos.ff][pos.ss] == 'A') d = (d + 1) % 4;
if (c[pos.ff][pos.ss] == 'C') d = (d + 3) % 4;
if (was2[d][pos] <= dst) {
return {-1, -1};
}
was2[d][pos] = dst;
pii p = pos;
p.ff += dir[d].ff;
p.ss += dir[d].ss;
if (p.ff > n || p.ss > m || p.ff < 1 || p.ss < 1 || c[p.ff][p.ss] == 'x') {
d2[pos.ff][pos.ss] = min(d2[pos.ff][pos.ss], dst);
return pos;
}
return dfs2(p, d, dst);
}
main() {
//freopen("triangles.in", "r", stdin);
//freopen("triangles.out", "w", stdout);
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
int x;
cin >> x >> m >> n;
pii pos1, pos2;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> c[i][j];
was1[0][{i, j}] = inf, was2[0][{i, j}] = inf;
was1[1][{i, j}] = inf, was2[1][{i, j}] = inf;
was1[2][{i, j}] = inf, was2[2][{i, j}] = inf;
was1[3][{i, j}] = inf, was2[3][{i, j}] = inf;
d1[i][j] = d2[i][j] = inf;
if (c[i][j] == '1') pos1 = {i, j};
if (c[i][j] == '2') pos2 = {i, j};
}
}
queue<pii> q;
q.push(pos1);
d1[pos1.ff][pos1.ss] = 0;
while (!q.empty()) {
pii cur = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
pii a = dfs1(cur, i, d1[cur.ff][cur.ss] + 1);
if (a.ff != -1) {
q.push(a);
}
}
}
q.push(pos1);
d2[pos2.ff][pos2.ss] = 0;
while (!q.empty()) {
pii cur = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
pii a = dfs2(cur, i, d2[cur.ff][cur.ss] + 1);
if (a.ff != -1) {
q.push(a);
}
}
}
int mn = inf;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) mn = min(mn, d1[i][j] + d2[i][j]);
}
if (mn == inf) mn = -1;
cout << mn;
}
Compilation message
robots.cpp:78:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
78 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
320 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
312 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
320 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
312 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
320 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
312 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
320 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
312 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
