oj.uz

답안 #891699

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
891699 2023-12-23T17:03:55 Z ind1v Patkice II (COCI21_patkice2) C++11
110 / 110
 221 ms 49236 KB 
#include <bits/stdc++.h>

using namespace std;

const short di[4] = {-1, 0, +1, 0};
const short dj[4] = {0, +1, 0, -1};
const char mv[4] = {'^', '>', 'v', '<'};

short n, m;
char a[2005][2005];
short sx, sy, ex, ey;
int d[2005][2005];
bool prc[2005][2005];
pair<short, short> par[2005][2005];

template<typename T>
inline bool minimize(T &x, const T &y) {
  if (x > y) {
    x = y;
    return true;
  }
  return false;
}

void bfs() {
  for (short i = 1; i <= n; i++) {
    for (short j = 1; j <= m; j++) {
      d[i][j] = 1000000000;
    }
  }
  d[sx][sy] = 0;
  deque<pair<short, short>> dq;
  dq.push_back(make_pair(sx, sy));
  while (!dq.empty()) {
    short x = dq.front().first;
    short y = dq.front().second;
    dq.pop_front();
    if (prc[x][y]) {
      continue;
    }
    prc[x][y] = true;
    if (a[x][y] == 'o') {
      for (short dir = 0; dir < 4; dir++) {
        short nx = x + di[dir];
        short ny = y + dj[dir];
        if (1 <= nx && nx <= n && 1 <= ny && ny <= m) {
          if (minimize(d[nx][ny], d[x][y])) {
            par[nx][ny] = make_pair(x, y);
            dq.push_front(make_pair(nx, ny));
          }
        }
      }
    } else {
      for (short dir = 0; dir < 4; dir++) {
        short nx = x + di[dir];
        short ny = y + dj[dir];
        short w = (mv[dir] != a[x][y]);
        if (w == 0) {
          if (1 <= nx && nx <= n && 1 <= ny && ny <= m) {
            if (minimize(d[nx][ny], d[x][y])) {
              par[nx][ny] = make_pair(x, y);
              dq.push_front(make_pair(nx, ny));
            }
          }
        } else if (w == 1) {
          if (1 <= nx && nx <= n && 1 <= ny && ny <= m) {
            if (minimize(d[nx][ny], d[x][y] + 1)) {
              par[nx][ny] = make_pair(x, y);
              dq.push_back(make_pair(nx, ny));
            }
          }         
        }
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (short i = 1; i <= n; i++) {
    for (short j = 1; j <= m; j++) {
      cin >> a[i][j];
      if (a[i][j] == 'o') {
        sx = i;
        sy = j;
      } else if (a[i][j] == 'x') {
        ex = i;
        ey = j;
      }
    }
  }
  bfs();
  cout << d[ex][ey] << '\n';
  while (make_pair(ex, ey) != make_pair(sx, sy)) {
    short xx = par[ex][ey].first;
    short yy = par[ex][ey].second;
    for (short dir = 0; dir < 4; dir++) {
      if (xx + di[dir] == ex && yy + dj[dir] == ey) {
        if (a[xx][yy] != 'o') {
          a[xx][yy] = mv[dir];
        }
        break;
      }
    }
    ex = xx;
    ey = yy;
  }
  for (short i = 1; i <= n; i++) {
    for (short j = 1; j <= m; j++) {
      cout << a[i][j];
    }
    cout << '\n';
  }
  return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct

Subtask #2
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 33 ms 16980 KB Output is correct
7 Correct 35 ms 26704 KB Output is correct
8 Correct 85 ms 29780 KB Output is correct
9 Correct 125 ms 39668 KB Output is correct
10 Correct 206 ms 44596 KB Output is correct
11 Correct 221 ms 49236 KB Output is correct