oj.uz

Submission #1104364

# Submission time Handle Problem Language Result Execution time Memory
1104364 2024-10-23T14:02:53 Z ALTAKEXE Robots (APIO13_robots) C++17
10 / 100
 2 ms 4432 KB 
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define inf INT_MAX
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FAR(i, a, b) for (ll i = (a); i >= (b); i--)
#define all(x) (x.begin(), x.end())
using namespace std;
const ll MAXN = 505;
const ll INF = 1e18;
pair<ll, ll> nx[MAXN][MAXN][4];
ll dis[MAXN][MAXN][10];
ll N, W, H, cnt;
char A[MAXN][MAXN];
pair<ll, ll> robots[10];
int main()
{
  cin >> N >> W >> H;
  for (ll i = 1; i <= H; ++i)
    for (ll 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 (ll i = 1; i <= H; ++i)
  {
    nx[i][W + 1][0] = make_pair(i, W);
    for (ll 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 (ll 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 (ll j = 1; j <= W; ++j)
  {
    nx[H + 1][j][2] = make_pair(H, j);
    for (ll 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 (ll 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];
    }
  }
  for (ll k = 0; k < cnt; ++k)
    for (ll i = 1; i <= H; ++i)
      for (ll j = 1; j <= W; ++j)
        dis[i][j][k] = INF;

  for (ll i = 0; i < cnt; ++i)
  {
    queue<pair<ll, ll>> q;
    q.push(robots[i]);
    dis[robots[i].first][robots[i].second][i] = 0;

    while (q.size())
    {
      pair<ll, ll> cur = q.front();
      q.pop();

      for (ll k = 0; k < 4; ++k)
      {
        pair<ll, ll> 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);
      }
    }
  }

  ll ans = INF;
  for (ll i = 1; i <= H; ++i)
    for (ll j = 1; j <= W; ++j)
    {
      ans = min(ans, dis[i][j][0] + dis[i][j][1]);
    }
  cout << (ans == INF ? -1 : ans) << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 1 ms 4432 KB Output is correct
5 Correct 2 ms 4432 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 40.0

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