Submission #1098072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098072		dzuizz	Robots (APIO13_robots)	C++14	10 / 100	1 ms	348 KiB

robots

#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;

  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==INF?-1:ans) << '\n';
}

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