# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1098064 | dzuizz | Robots (APIO13_robots) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <cstring>
using namespace std;
//#define DEBUG false
#define int long long
const int MAXN = 505;
const int INF = 1e18;
pair<int,int> nx[MAXN][MAXN][4]; // right, left, up, down
int dis[MAXN][MAXN][10];
int N, W, H, cnt;
char A[MAXN][MAXN];
pair<int,int> robots[10];
signed main() {
// Subtask 1
cin >> N >> W >> H;
memset(nx, -1, sizeof nx);
for (int i=1; i<=H; ++i) for (int j=1; j<=W; ++j) {
cin >> A[i][j];
if ('0' < A[i][j] && A[i][j] <= '9')
robots[A[i][j]-'1'] = make_pair(i,j), ++cnt;
}
for (int i=1; i<=H; ++i) {
nx[i][W+1][0] = make_pair(i, W);
for (int j=W; j>0; --j) {
if (A[i][j] == 'x') nx[i][j][0] = make_pair(i, j-1);
else nx[i][j][0] = nx[i][j+1][0];
}
nx[i][0][1] = make_pair(i, 1);
for (int j=1; j<=W; ++j) {
if (A[i][j] == 'x') nx[i][j][1] = make_pair(i, j+1);
else nx[i][j][1] = nx[i][j-1][1];
}
}
for (int j=1; j<=W; ++j) {
nx[H+1][j][2] = make_pair(H, j);
for (int i=H; i>0; --i) {
if (A[i][j] == 'x') nx[i][j][2] = make_pair(i-1, j);
else nx[i][j][2] = nx[i+1][j][2];
}
nx[0][j][3] = make_pair(1, j);
for (int i=1; i<=H; ++i) {
if (A[i][j] == 'x') nx[i][j][3] = make_pair(i+1, j);
else nx[i][j][3] = nx[i-1][j][3];
}
}
#ifdef DEBUG // nx array check
for (int k=0; k<4; ++k) { for (int i=1; i<=H; ++i) { for (int j=1; j<=W; ++j) cout << nx[i][j][k].first << nx[i][j][k].second << " "; cout << '\n'; } cout << '\n'; }
#endif
for (int k=0; k<cnt; ++k) for (int i=1; i<=H; ++i) for (int j=1; j<=W; ++j)
dis[i][j][k] = INF;
for (int i=0; i<cnt; ++i) {
queue<pair<int,int> > q;
q.push(robots[i]);
dis[robots[i].first][robots[i].second][i] = 0;
while (q.size()) {
pair<int,int> cur = q.front(); q.pop();
for (int k=0; k<4; ++k) {
pair<int,int> p = nx[cur.first][cur.second][k];
if (p.first == cur.first && p.second == cur.second) continue;
if (dis[p.first][p.second][i] < dis[cur.first][cur.second][i]+1) continue;
dis[p.first][p.second][i] = dis[cur.first][cur.second][i] + 1;
q.push(p);
}
}
}
#ifdef DEBUG // dis array check
for (int k=0; k<cnt; ++k) { for (int i=1; i<=H; ++i) { for (int j=1; j<=W; ++j) cout << dis[i][j][k] << " "; cout << '\n'; } cout << '\n'; }
#endif
int ans=INF;
for (int i=1; i<=H; ++i) for (int j=1; j<=W; ++j) {
ans = min(ans, dis[i][j][0] + dis[i][j][1]);
}
cout << ans << '\n';
}