Submission #1165156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165156		JelalTkm	Robots (APIO13_robots)	C++20	30 / 100	1596 ms	12204 KiB

robots

#include <bits/stdc++.h>
// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")

using namespace std;

#define int long long int

const int N = 3e2 + 10;
const int md = 1e9 + 7;
const int INF = 1e18;

struct node {
  int x;
  int y;
  char nap;
};

int con(char c) {
  if (c == '>')
    return 0;
  else if (c == '<')
    return 1;
  else if (c == '^')
    return 2;
  else 
    return 3;
}

int n, m;
vector<vector<char>> a(N, vector<char> (N));

bool check(int x, int y) {
  return (x >= 1 && y >= 1 && x <= n && y <= m);
}

node f(int x, int y, char nap) {
  int nx = x, ny = y;
  char nnap = nap;
  if (a[x][y] != 'A' && a[x][y] != 'C' && a[x][y] != 'x') {
    if (nap == '>')
      ny++;
    if (nap == '<')
      ny--;
    if (nap == '^')
      nx--;
    if (nap == 'v')
      nx++;
  } else {
    if (a[x][y] == 'A') {
      if (nap == '>') {
        nnap = '^';
        nx--;
      }
      if (nap == '<') {
        nnap = 'v';
        nx++;
      }
      if (nap == '^') {
        nnap = '<';
        ny--;
      }
      if (nap == 'v') {
        nnap = '>';
        ny++;
      }
    } else if (a[x][y] == 'C') {
      if (nap == '>') {
        nnap = 'v';
        nx++;
      }
      if (nap == '<') {
        nnap = '^';
        nx--;
      }
      if (nap == '^') {
        nnap = '>';
        ny++;
      }
      if (nap == 'v') {
        nnap = '<';
        ny--;
      }
    }
  }

  if (check(nx, ny) && a[nx][ny] != 'x')
    return {nx, ny, nnap};
  else return {x, y, nnap};
}

map<pair<int, int>, int> bfs(int x, int y) {
  queue<node> q;
  queue<int> cou;
  map<pair<int, int>, int> mp;
  if (a[x][y] == 'x')
    return mp;
  vector<vector<vector<bool>>> visited(n + 1, vector<vector<bool>> (m + 1, vector<bool> (4)));
  q.push({x, y, '>'}); visited[x][y][0] = 1;
  q.push({x, y, '<'}); visited[x][y][1] = 1;
  q.push({x, y, '^'}); visited[x][y][2] = 1;
  q.push({x, y, 'v'}); visited[x][y][3] = 1;
  cou.push(1);cou.push(1);cou.push(1);cou.push(1);
  mp[{x, y}] = INF;

  while (!q.empty()) {
    auto [xx, yy, nn] = q.front();
    int cn = cou.front();
    q.pop();cou.pop();
    auto v = f(xx, yy, nn);
    if (v.x == xx && v.y == yy) {
      if (mp[{xx, yy}] == 0)
        mp[{xx, yy}] = cn;
      if (!visited[v.x][v.y][0]) {
        q.push({v.x, v.y, '>'}); visited[v.x][v.y][0] = 1;
        visited[v.x][v.y][0] = 1;
        cou.push(cn + 1);
      }
      if (!visited[v.x][v.y][1]) {
        q.push({v.x, v.y, '<'}); visited[v.x][v.y][1] = 1;
        visited[v.x][v.y][1] = 1;
        cou.push(cn + 1);
      }
      if (!visited[v.x][v.y][2]) {
        q.push({v.x, v.y, '^'}); visited[v.x][v.y][2] = 1;
        visited[v.x][v.y][2] = 1;
        cou.push(cn + 1);
      }
      if (!visited[v.x][v.y][3]) {
        q.push({v.x, v.y, 'v'}); visited[v.x][v.y][3] = 1;
        visited[v.x][v.y][3] = 1;
        cou.push(cn + 1);
      }
    } else {
      if (!visited[v.x][v.y][con(v.nap)]) {
        q.push(v);
        visited[v.x][v.y][con(v.nap)] = 1;
        cou.push(cn);
      }
    }
  }

  return mp;
}

int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T = 1;
  // cin >> T;
  while (T--) {
    int c;
    cin >> c >> m >> n;
    vector<pair<int, int>> nu(10);
    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')
          nu[(a[i][j] - '0')] = {i, j};
      }

    if (c == 1) {
      cout << 0 << '\n';
      continue;
    }

    map<pair<int, int>, int> mp1, mp2;
    for (int i = 1; i <= c; i++) {
      auto [x, y] = nu[i];
      if (i == 1)
        mp1 = bfs(x, y);
      else mp2 = bfs(x, y);
    }

    int ans = INF;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        for (int k = 1; k <= n; k++) {
          for (int l = 1; l <= m; l++) {
            int fi = mp1[{k, l}], se = mp2[{k, l}];
            if (i == k && j == l) {
              if (fi != 0 && se != 0) {
                ans = min(ans, (fi == INF ? 0 : fi) + (se == INF ? 0 : se));
              }
              continue;
            }
            if (fi != 0 && se != 0) {
              auto mp = bfs(k, l);
              int th = mp[{i, j}];
              if (th != 0) {
                ans = min(ans, (fi == INF ? 0 : fi) + (se == INF ? 0 : se) + (th == INF ? 0 : th));
              }
            }
          }
        }
      }
    }

    cout << (ans == INF ? -1 : ans) << '\n';
  }
 
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40