oj.uz

Submission #1004027

# Submission time Handle Problem Language Result Execution time Memory
1004027 2024-06-21T02:23:57 Z TranThuMinh Patkice II (COCI21_patkice2) C++17
0 / 110
 1 ms 6492 KB 
#include<bits/stdc++.h>

#define tp tuple<int, int, int>

using namespace std;

const int N = 2e3 + 5,
          INF = 1e9;

int dx[4] = {0, 0, -1, 1},
    dy[4] = {-1, 1, 0, 0};

char conv[4] = {'<', '>', '^', 'v'};

int m, n, stx, sty, edx, edy;
int d[N][N];
tp pre[N][N];
char a[N][N];

int id(char s) {
  if(s == '<') return 0;
  if(s == '>') return 1;
  if(s == '^') return 2;
  if(s == 'v') return 3;
}

bool out(int x, int y) {
  return (!x || !y || x > m || y > n || a[x][y] == 'o');
}

void bfs() {
  for(int x = 1; x <= m; ++x)
    for(int y = 1; y <= n; ++y) d[x][y] = INF;

  deque<tp> q;
  q.push_back({stx, sty, 0});
  d[stx][sty] = 0;

  while(q.size()) {
    int x, y, w; tie(x, y, w) = q.front();
    q.pop_front();

    for(int i = 0; i < 4; ++i) {
      int nx = x + dx[i],
          ny = y + dy[i],
          cost = (a[x][y] != 'o' && i != id(a[x][y]));

      if(out(nx, ny)) continue;

      if(d[nx][ny] > w + cost) {
        d[nx][ny] = w + cost;
        pre[nx][ny] = {x, y, i};

        if(!cost) q.push_front({nx, ny, d[nx][ny]});
        else q.push_back({nx, ny, d[nx][ny]});
      }
    }
  }
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  if(fopen("task.inp", "r")) {
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
  }

  cin >> m >> n;

  for(int i = 1; i <= m; ++i) {
    for(int j = 1; j <= n; ++j) {
        cin >> a[i][j];

        if(a[i][j] == 'o') stx = i, sty = j;
        if(a[i][j] == 'x') edx = i, edy = j;
    }
  }

  for(int i = 1; i <= m; ++i)
    for(int j = 1; j <= n; ++j) pre[i][j] = {INF, INF, INF};

  bfs();
  cout << d[edx][edy] << '\n';

  int x, y, l; tie(x, y, l) = pre[edx][edy];

  while(x != INF) {
    if(a[x][y] == 'o') break;

    if(a[x][y] != conv[l]) a[x][y] = conv[l];
    tie(x, y, l) = pre[x][y];
  }

  for(int i = 1; i <= m; ++i) {
    for(int j = 1; j <= n; ++j) cout << a[i][j];
    cout << '\n';
  }

}

Compilation message

Main.cpp: In function 'int id(char)':
Main.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
   25 | }
      | ^
Main.cpp: In function 'int main()':
Main.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     freopen("task.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen("task.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Partially correct 1 ms 6492 KB Partially correct
5 Incorrect 1 ms 4444 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Partially correct 1 ms 6492 KB Partially correct
5 Incorrect 1 ms 4444 KB Output isn't correct
6 Halted 0 ms 0 KB -