oj.uz

Submission #42233

# Submission time Handle Problem Language Result Execution time Memory
42233 2018-02-23T19:48:59 Z gabrielsimoes Portals (BOI14_portals) C++14
0 / 100
 2 ms 620 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 210, INF = 1e9;
typedef pair<int, int> pii;

int n, m;
bool open[MAXN][MAXN];
pii start, cake;

// int ix(pii p) { return (p.first - 1) * m + p.second - 1; }
// pii pr(int ix) { return pii(ix / m + 1, (ix % n) + 1); }

// left, right, north, south
int limit[MAXN][MAXN][4];
bool ok[MAXN][MAXN];
int dist[MAXN][MAXN];

int bfs() {
  for (int i = 1; i <= n; i++)
    for (int k = 1; k <= m; k++) dist[i][k] = INF;

  queue<pii> q;
  q.push(start);
  dist[start.first][start.second] = 0;
  while (!q.empty()) {
    int x, y;
    tie(x, y) = q.front();
    q.pop();

    for (int i = 0; i < 8; i++) {
      int nx = x, ny = y;
      if (i == 0) nx--;
      if (i == 1) nx++;
      if (i == 2) ny--;
      if (i == 3) ny++;
      if (i == 4) nx -= limit[x][y][0];
      if (i == 5) nx += limit[x][y][1];
      if (i == 6) ny -= limit[x][y][2];
      if (i == 7) ny += limit[x][y][3];

      if (open[nx][ny] && !ok[nx][ny]) {
        dist[nx][ny] = dist[x][y] + 1;
        ok[nx][ny] = 1;
        q.push(pii(nx, ny));
      }
    }
  }

  return dist[cake.first][cake.second];
}

int main() {
  scanf("%d %d", &n, &m);
  char c;
  for (int i = 1; i <= n; i++) {
    for (int k = 1; k <= m; k++) {
      scanf(" %c", &c);
      if (c != '#') open[i][k] = 1;
      if (c == 'S') start = pii(i, k);
      if (c == 'C') cake = pii(i, k);
    }
  }

  for (int i = 1; i <= n; i++) {
    int last_wall = 0;
    for (int k = 1; k <= m; k++) {
      if (open[i][k])
        limit[i][k][0] = k - last_wall - 1;
      else
        last_wall = k;
    }

    last_wall = m + 1;
    for (int k = m; k >= 1; k--) {
      if (open[i][k])
        limit[i][k][1] = last_wall - k - 1;
      else
        last_wall = k;
    }
  }

  for (int k = 1; k <= m; k++) {
    int last_wall = 0;
    for (int i = 1; i <= n; i++) {
      if (open[i][k])
        limit[i][k][2] = i - last_wall - 1;
      else
        last_wall = i;
    }

    last_wall = n + 1;
    for (int i = n; i >= 1; i--) {
      if (open[i][k])
        limit[i][k][3] = last_wall - i - 1;
      else
        last_wall = i;
    }
  }

  printf("%d\n", bfs());
}

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:54:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
                         ^
portals.cpp:58:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf(" %c", &c);
                       ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Incorrect 1 ms 564 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 564 KB Output is correct
2 Correct 2 ms 576 KB Output is correct
3 Incorrect 1 ms 620 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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