Submission #1194267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194267		zNatsumi	Patkice II (COCI21_patkice2)	C++20	110 / 110	241 ms	58716 KiB

Main

#include <bits/stdc++.h>

using namespace std;
const int N = 2e3+5,
          inf = 1e9,
          mod = 1e9 + 7;
const int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
#define fi first
#define se second
#define all(x) x.begin(), x.end()

int m, n, a[N][N], f[N][N], trace[N][N];
ii st, ed;

int in(){
  char x; cin >> x;
  if(x == '^') return 0;
  if(x == 'v') return 1;
  if(x == '<') return 2;
  if(x == '>') return 3;
  if(x == '.') return 4;
  if(x == 'o') return 5;
  if(x == 'x') return 6;
}

int32_t main()
{
  ios_base::sync_with_stdio(0); cin.tie(0);
  cout.tie(0);

//  #define task "test"
//  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++){
    a[i][j] = in();
    if(a[i][j] == 5) st = {i, j};
    if(a[i][j] == 6) ed = {i, j};
    f[i][j] = inf;
  }
  f[st.fi][st.se] = 0;

  deque<iii> dq;
  dq.emplace_back(0, st.fi, st.se);

  while(dq.size()){
    int d, r, c; tie(d, r, c) = dq.front(); dq.pop_front();

    if(make_pair(r, c) == ed){
      cout << f[r][c] << "\n";
      break;
    }
    if(d != f[r][c]) continue;

    for(int i = 0; i < 4; i++){
      int nr = r + dr[i], nc = c + dc[i];
      if(nr < 1 || nc < 1 || nr > m || nc > n) continue;
      int cost = (a[r][c] != i && a[r][c] != 5);

      if(f[nr][nc] > f[r][c] + cost){
        if(cost) dq.emplace_back(f[nr][nc] = f[r][c] + cost, nr, nc);
        else dq.emplace_front(f[nr][nc] = f[r][c] + cost, nr, nc);

        if(i == 0) trace[nr][nc] = 1;
        if(i == 1) trace[nr][nc] = 0;
        if(i == 2) trace[nr][nc] = 3;
        if(i == 3) trace[nr][nc] = 2;
      }
    }
  }
  while(1){
    int i = trace[ed.fi][ed.se];
    int nr = ed.fi + dr[i], nc = ed.se + dc[i];

    if(a[nr][nc] == 5) break;
    if(i == 0) a[nr][nc] = 1;
    if(i == 1) a[nr][nc] = 0;
    if(i == 2) a[nr][nc] = 3;
    if(i == 3) a[nr][nc] = 2;
    ed = make_pair(nr, nc);
  }
  for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++){
    if(a[i][j] == 0) cout << '^';
    if(a[i][j] == 1) cout << 'v';
    if(a[i][j] == 2) cout << '<';
    if(a[i][j] == 3) cout << '>';
    if(a[i][j] == 4) cout << '.';
    if(a[i][j] == 5) cout << 'o';
    if(a[i][j] == 6) cout << 'x';
    if(j == n) cout << '\n';
  }

  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int in()':
Main.cpp:26:1: warning: control reaches end of non-void function [-Wreturn-type]
   26 | }
      | ^

• Subtask 1: 30 / 30
• Subtask 2: 80 / 80