#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define ll long long
const int N = 505;
char a[N][N];
int b[10][N][N], n, w, h;
struct ab {
int x, y, k;
};
pair <int, int> f1(int i, int j, int x1, int y1) {
while(a[i + x1][j + y1] != 'x' and i + x1 <= h and i + x1 > 0 and j + y1 <= w and j + y1 > 0) {
i += x1, j += y1;
if(a[i][j] == 'C') {
if(x1 == -1 and y1 == 0) x1 = 0, y1 = 1;
else if(x1 == 0 and y1 == 1) x1 = 1, y1 = 0;
else if(x1 == 1 and y1 == 0) x1 = 0, y1 = -1;
else if(x1 == 0 and y1 == -1) x1 = -1, y1 = 0;
}
if(a[i][j] == 'A') {
if(x1 == -1 and y1 == 0) x1 = 0, y1 = -1;
else if(x1 == 0 and y1 == 1) x1 = -1, y1 = 0;
else if(x1 == 1 and y1 == 0) x1 = 0, y1 = 1;
else if(x1 == 0 and y1 == -1) x1 = 1, y1 = 0;
}
}
return {i, j};
}
void f(int c, int i, int j) {
queue <ab> q;
ab abb;
abb.x = i, abb.y = j, abb.k = 0;
b[c][i][j] = 0;
q.push(abb);
while(!q.empty()) {
ab z = q.front();
q.pop();
if(b[c][z.x][z.y] != z.k) continue;
pair <int, int> ind = f1(z.x, z.y, 1, 0);
if(b[c][ind.ff][ind.ss] > z.k + 1){
abb.x = ind.ff, abb.y = ind.ss, abb.k = z.k+1;
b[c][ind.ff][ind.ss] = z.k+1;
q.push(abb);
}
ind = f1(z.x, z.y, 0, 1);
if(b[c][ind.ff][ind.ss] > z.k + 1){
abb.x = ind.ff, abb.y = ind.ss, abb.k = z.k+1;
b[c][ind.ff][ind.ss] = z.k+1;
q.push(abb);
}
ind = f1(z.x, z.y, -1, 0);
if(b[c][ind.ff][ind.ss] > z.k + 1){
abb.x = ind.ff, abb.y = ind.ss, abb.k = z.k+1;
b[c][ind.ff][ind.ss] = z.k+1;
q.push(abb);
}
ind = f1(z.x, z.y, 0, -1);
if(b[c][ind.ff][ind.ss] > z.k + 1){
abb.x = ind.ff, abb.y = ind.ss, abb.k = z.k+1;
b[c][ind.ff][ind.ss] = z.k+1;
q.push(abb);
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> w >> h;
for(int i = 1; i <= h; i++) {
for(int j = 1; j <= w; j++) {
cin >> a[i][j];
for(int ij = 1; ij <= n; ij++) {
b[ij][i][j] = 1e9;
}
}
}
for(int i = 1; i <= h; i++) {
for(int j = 1; j <= w; j++) {
if(a[i][j] >= '1' and a[i][j] <= '9') {
f((a[i][j] - '0'), i, j);
}
}
}
ll ans = 0;
for(int o = 1; o < n; o++) {
ll oo = 1e9;
pair <int, int> bb, in;
for(int x1 = 1; x1 < n; x1++) {
for(int x2 = x1+1; x2 <= n; x2++) {
for(int i = 1; i <= h; i++) {
for(int j = 1; j <= w; j++) {
if(oo > b[x1][i][j] + b[x2][i][j]) {
oo = b[x1][i][j] + b[x2][i][j];
bb = {x1, x2};
in = {i, j};
}
}
}
}
}
if(oo == 1e9) {
cout << -1;
return 0;
}
ans += oo;
cout << bb.ff << ' ' << bb.ss << ' ' << oo << '\n';
for(int i = 1; i <= h; i++) {
for(int j = 1; j <= w; j++) {
b[bb.ff][i][j] = 1e9;
b[bb.ss][i][j] = 1e9;
}
}
f(bb.ff, in.ff, in.ss);
}
cout << ans;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |