#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) x.begin(), x.end()
#define pb push_back
#define x first
#define y second
#define int long long
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
using namespace std;
typedef long long ll;
const int maxn = 507;
const int K = 1e5;
const int mod = 1e9 + 7;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int s, n, m, temp;
char a[maxn][maxn];
vector <pair <int, int>> act;
pair <int, int> up[maxn][maxn];
pair <int, int> down[maxn][maxn];
pair <int, int> L[maxn][maxn];
pair <int, int> R[maxn][maxn];
vector <pair <int, int>> g[maxn][maxn];
bool used[maxn][maxn];
int dist[maxn][maxn];
int cur[maxn][maxn][10];
void solve() {
cin >> s >> m >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
if (a[i][j] >= '1' && a[i][j] <= '9') {
act.pb({i, j});
}
}
}
for (int i = 1; i <= n; i++) {
L[i][0] = {i, 1};
for (int j = 1; j <= m; j++) {
L[i][j] = L[i][j - 1];
if (a[i][j] == 'x') L[i][j] = {i, j + 1};
if (a[i][j] == 'A' || a[i][j] == 'C') L[i][j] = {i, j};
}
R[i][m + 1] = {i, m};
for (int j = m; j >= 1; j--) {
R[i][j] = R[i][j + 1];
if (a[i][j] == 'x') R[i][j] = {i, j - 1};
if (a[i][j] == 'A' || a[i][j] == 'C') R[i][j] = {i, j};
}
}
for (int j = 1; j <= m; j++) {
up[0][j] = {1, j};
for (int i = 1; i <= n; i++) {
up[i][j] = up[i - 1][j];
if (a[i][j] == 'x') up[i][j] = {i + 1, j};
if (a[i][j] == 'A' || a[i][j] == 'C') up[i][j] = {i, j};
}
down[n + 1][j] = {n, j};
for (int i = n; i >= 1; i--) {
down[i][j] = down[i + 1][j];
if (a[i][j] == 'x') down[i][j] = {i - 1, j};
if (a[i][j] == 'A' || a[i][j] == 'C') down[i][j] = {i, j};
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] == 'x') continue;
g[i][j].pb(L[i][j]);
g[i][j].pb(R[i][j]);
g[i][j].pb(up[i][j]);
g[i][j].pb(down[i][j]);
}
}
for (auto [rx, ry] : act) {
queue <pair <int, int>> q;
q.push({rx, ry}); used[rx][ry] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dist[i][j] = 1e18;
}
}
dist[rx][ry] = 0;
while (q.size()) {
pair <int, int> v = q.front();
q.pop();
for (auto [tox, toy] : g[v.x][v.y]) {
if (!used[tox][toy]) {
used[tox][toy] = 1;
dist[tox][toy] = dist[v.x][v.y] + 1;
q.push({tox, toy});
}
}
}
++temp;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cur[i][j][temp] = dist[i][j];
dist[i][j] = 1e18;
used[i][j] = 0;
}
}
}
int ans = 1e18;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
bool check = 1;
for (int t = 1; t <= temp; t++) {
if (cur[i][j][t] == 1e18) {
check = 0;
break;
}
}
if (!check) continue;
int res = 0;
for (int t = 1; t <= temp; t++) {
res += cur[i][j][t];
}
ans = min(ans, res);
}
}
if (ans == 1e18) {
cout << -1;
return;
}
cout << ans;
}
//1 -> L
//2 -> R
//3 -> up
//4 -> down
/*
4 10 5
1.........
xx...x4...
..x..x....
2....x....
..x.3.x...
*/
const bool cases = 0;
signed main() {
speed;
int test = 1, cnt = 0;
if (cases) cin >> test;
while (test--) {
// cout << "Case " << ++cnt << ": ";
solve();
}
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:151:16: warning: unused variable 'cnt' [-Wunused-variable]
151 | int test = 1, cnt = 0;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6760 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6760 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6760 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6760 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
