oj.uz

Submission #480016

# Submission time Handle Problem Language Result Execution time Memory
480016 2021-10-14T09:19:38 Z howboutsleep Patkice (COCI20_patkice) C++17
50 / 50
 1 ms 716 KB 
#include <bits/stdc++.h>

#define ll long long
#define F first
#define S second
#define NUM 101
#define MOD 1000000007

using namespace std;

vector <pair<int, int> > gr [NUM][NUM];
bool pos;

int starti, startj, endi, endj, cnt;

void dfs (int i, int j) {
  //cout << i << ' ' << j << endl;
  cnt ++;
  if (i == endi && j == endj) {
    return;
  }
  if (gr[i][j].empty()) {
    pos = 0;
    return;
  }
  for (auto nxt : gr[i][j]) {
    dfs(nxt.F, nxt.S);
  }
  return;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i ++) {
    for (int j = 0; j < m; j ++) {
      char c;
      cin >> c;
      if (c == 'o') {
        starti = i;
        startj = j;
      }
      if (c == 'x') {
        endi = i;
        endj = j;
      }
      if (c == '^') {
        gr[i][j].push_back({i - 1, j});
      }
      if (c == 'v') {
        gr[i][j].push_back({i + 1, j});
      }
      if (c == '<') {
        gr[i][j].push_back({i, j - 1});
      }
      if (c == '>') {
        gr[i][j].push_back({i, j + 1});
      }
    }
  }
  int minn = 100000;
  string res;
  if (startj < m - 1) {
    pos = 1;
    cnt = 0;
    dfs(starti, startj + 1);
    if (pos) {
      if (minn > cnt) {
        res = 'E';
        minn = cnt;
      }
    }
  }
  //cout << endl;
  if (starti > 0) {
    pos = 1;
    cnt = 0;
    dfs(starti - 1, startj);
    if (pos) {
      if (minn > cnt) {
        res = 'N';
        minn = cnt;
      }
    }
  }
  //cout << endl;
  if (starti < n - 1) {
    pos = 1;
    cnt = 0;
    dfs(starti + 1, startj);
    if (pos) {
      if (minn > cnt) {
        res = 'S';
        minn = cnt;
      }
    }
  }
  //cout << endl;
  
  if (startj > 0) {
    pos = 1;
    cnt = 0;
    dfs(starti, startj - 1);
    if (pos) {
      if (minn > cnt) {
        res = 'W';
        minn = cnt;
      }
    }
  }
  //cout << endl;

  if (minn < 100000) {
    cout << ":)" << endl << res;
  }
  else cout << ":(";
  
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 560 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 560 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 556 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 1 ms 588 KB Output is correct
14 Correct 1 ms 588 KB Output is correct
15 Correct 1 ms 588 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct