oj.uz

Submission #1098071

# Submission time Handle Problem Language Result Execution time Memory
1098071 2024-10-09T03:11:36 Z dzuizz Robots (APIO13_robots) C++14
0 / 100
 7 ms 16220 KB 
#include <iostream>
#include <cstring>
#include <queue>
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';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16220 KB Output is correct
2 Incorrect 7 ms 16220 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16220 KB Output is correct
2 Incorrect 7 ms 16220 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16220 KB Output is correct
2 Incorrect 7 ms 16220 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16220 KB Output is correct
2 Incorrect 7 ms 16220 KB Output isn't correct
3 Halted 0 ms 0 KB -