제출 #480016

#제출 시각아이디문제언어결과실행 시간메모리
480016howboutsleepPatkice (COCI20_patkice)C++17
50 / 50
1 ms716 KiB
#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 << ":(";
  
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...