oj.uz

답안 #587944

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
587944 2022-07-02T14:39:09 Z MilosMilutinovic Patkice II (COCI21_patkice2) C++14
110 / 110
 988 ms 60248 KB 
/**
 *    author:  wxhtzdy
 *    created: 02.07.2022 16:23:36
**/
#include <bits/stdc++.h>

using namespace std;

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m;
  cin >> n >> m;
  vector<string> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  int sx, sy, fx, fy;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (s[i][j] == 'o') {
        sx = i;
        sy = j;
      }
      if (s[i][j] == 'x') {
        fx = i;
        fy = j;
      }
    }
  }        
  const int inf = (int) 1e7;
  vector<vector<int>> dist(n, vector<int>(m, inf));
  vector<int> prv(n * m, -1);
  set<pair<int, int>> st;
  dist[sx][sy] = 0;
  st.emplace(0, sx * m + sy);
  while (!st.empty()) {
    auto it = st.begin();
    int id = it->second;
    int i = id / m;
    int j = id % m;     
    st.erase(it);
    vector<int> cost(4, 1);
    if (s[i][j] == 'v') {
      cost[0] = 0;
    }
    if (s[i][j] == '>') {
      cost[1] = 0;
    }
    if (s[i][j] == '^') {
      cost[2] = 0;
    }
    if (s[i][j] == '<') {
      cost[3] = 0;
    }
    if (s[i][j] == 'o') {
      cost = vector<int>(4, 0);
    }
    for (int d = 0; d < 4; d++) {
      int ni = i + dx[d];
      int nj = j + dy[d];
      if (ni >= 0 && ni < n && nj >= 0 && nj < m && dist[ni][nj] > dist[i][j] + cost[d]) {
        if (dist[ni][nj] != inf) {
          st.erase(st.find(make_pair(dist[ni][nj], ni * m + nj)));
        }
        dist[ni][nj] = dist[i][j] + cost[d];
        prv[ni * m + nj] = i * m + j;
        st.emplace(make_pair(dist[ni][nj], ni * m + nj));
      }
    }
  }
  cout << dist[fx][fy] << '\n';
  int x = fx * m + fy;
  vector<int> path;
  while (x != -1) {
    path.push_back(x);
    x = prv[x];
  }
  for (int i = 1; i < (int) path.size() - 1; i++) {
    int xa = path[i] / m;
    int ya = path[i] % m;
    int xb = path[i - 1] / m;
    int yb = path[i - 1] % m;
    if (xa + 1 == xb) {
      s[xa][ya] = 'v';
    }
    if (xa - 1 == xb) {
      s[xa][ya] = '^';
    }
    if (ya + 1 == yb) {
      s[xa][ya] = '>'; 
    }
    if (ya - 1 == yb) {
      s[xa][ya] = '<';
    }
  }
  for (int i = 0; i < n; i++) {
    cout << s[i] << '\n';
  }
  return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:75:22: warning: 'fy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |   cout << dist[fx][fy] << '\n';
      |                      ^
Main.cpp:75:18: warning: 'fx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |   cout << dist[fx][fy] << '\n';
      |                  ^
Main.cpp:39:24: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |   st.emplace(0, sx * m + sy);
      |                 ~~~~~~~^~~~
Main.cpp:39:20: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |   st.emplace(0, sx * m + sy);
      |                 ~~~^~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 95 ms 5352 KB Output is correct
7 Correct 116 ms 9540 KB Output is correct
8 Correct 265 ms 13312 KB Output is correct
9 Correct 509 ms 32972 KB Output is correct
10 Correct 623 ms 31772 KB Output is correct
11 Correct 988 ms 60248 KB Output is correct