Submission #891699

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
891699	2023-12-23T17:03:55 Z	ind1v	Patkice II (COCI21_patkice2)	C++11	110 / 110	221 ms	49236 KB

Main

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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