Submission #42237

#	Time	Username	Problem	Language	Result	Execution time	Memory
42237		gabrielsimoes	Portals (BOI14_portals)	C++14	31 / 100	123 ms	32476 KiB

portals

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 52, 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][MAXN][MAXN];
int dist[MAXN][MAXN][MAXN][MAXN];

int bfs() {
  deque<tuple<int, int, int, int>> q;
  q.push_back(tuple<int, int, int, int>(start.first, start.second, 0, 0));
  dist[start.first][start.second][0][0] = 0;
  while (!q.empty()) {
    int x, y, px, py;
    tie(x, y, px, py) = q.front();
    q.pop_front();

    // printf("x %d y %d px %d py %d\n", x, y, px, py);

    if (x == cake.first && y == cake.second) {
      return dist[x][y][px][py];
    }

    bool haswall = 0;
    for (int i = 0; i < 8; i++) {
      int nx = x, ny = y;

      if (i < 4) {
        if (i == 0) ny--;
        if (i == 1) ny++;
        if (i == 2) nx--;
        if (i == 3) nx++;
        if (!open[nx][ny]) {
          haswall = true;
        } else if (!ok[nx][ny][px][py]) {
          dist[nx][ny][px][py] = dist[x][y][px][py] + 1;
          ok[nx][ny][px][py] = 1;
          q.push_back(tuple<int, int, int, int>(nx, ny, px, py));
        }
      }

      else {
        if (i == 4) ny -= limit[x][y][0];
        if (i == 5) ny += limit[x][y][1];
        if (i == 6) nx -= limit[x][y][2];
        if (i == 7) nx += limit[x][y][3];
        // printf("%d %d : %d %d\n", x, y, nx, ny);
        if (!ok[x][y][nx][ny]) {
          dist[x][y][nx][ny] = dist[x][y][px][py];
          ok[x][y][nx][ny] = 1;
          q.push_front(tuple<int, int, int, int>(x, y, nx, ny));
        }
      }
    }

    if (haswall && px != 0 && !ok[px][py][px][py]) {
      dist[px][py][px][py] = dist[x][y][px][py] + 1;
      ok[px][py][px][py] = 1;
      q.push_back(tuple<int, int, int, int>(px, py, px, py));
    }
  }

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

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 (stderr)

portals.cpp: In function 'int main()':
portals.cpp:77: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:81:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf(" %c", &c);
                       ^

• Subtask 1: 11 / 11
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30