oj.uz

Submission #587941

# Submission time Handle Problem Language Result Execution time Memory
587941 2022-07-02T14:33:05 Z MilosMilutinovic Patkice II (COCI21_patkice2) C++14
55 / 110
 846 ms 49740 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));
  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];
        st.emplace(make_pair(dist[ni][nj], ni * m + nj));
      }
    }
  }
  cout << dist[fx][fy] << '\n';
  for (int i = 0; i < n; i++) {
    cout << s[i] << '\n';
  }                                                   
  return 0;
}

Compilation message

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

Subtask #1
15.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Partially correct
2 Partially correct 0 ms 212 KB Partially correct
3 Partially correct 0 ms 212 KB Partially correct
4 Partially correct 0 ms 324 KB Partially correct
5 Partially correct 0 ms 212 KB Partially correct

Subtask #2
40.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Partially correct
2 Partially correct 0 ms 212 KB Partially correct
3 Partially correct 0 ms 212 KB Partially correct
4 Partially correct 0 ms 324 KB Partially correct
5 Partially correct 0 ms 212 KB Partially correct
6 Partially correct 92 ms 3892 KB Partially correct
7 Partially correct 132 ms 8016 KB Partially correct
8 Partially correct 238 ms 9376 KB Partially correct
9 Partially correct 499 ms 26560 KB Partially correct
10 Partially correct 596 ms 22352 KB Partially correct
11 Partially correct 846 ms 49740 KB Partially correct