Submission #587944

#	Time	Username	Problem	Language	Result	Execution time	Memory
587944		MilosMilutinovic	Patkice II (COCI21_patkice2)	C++14	110 / 110	988 ms	60248 KiB

Main

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

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 / 30
• Subtask 2: 80 / 80