oj.uz

Submission #460457

# Submission time Handle Problem Language Result Execution time Memory
460457 2021-08-09T07:03:07 Z benson0402 Patkice (COCI20_patkice) C++14
50 / 50
 1 ms 332 KB 
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define F first
#define S second
#define ALL(x) x.begin(), x.end()
#define MEM(x) memset(x, 0, sizeof(x))
#define MEMS(x) memset(x, -1, sizeof(x))

#define eb emplace_back
#define ep emplace
#define mkp make_pair

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
/*------------------------------------------------------------------*/
using pic = pair<int, char>;

const int N = 100 + 5;
char G[N][N];
bool vis[N][N];
pic ans[N][N];

int r, s, er, es, sr, ss;

bool check(int i, int j) {
	return !vis[i][j] && i >= 0 && i < r && j >= 0 && j < s;
}
// E > N > S > W
pic bfs(int i, int j) {
	queue<pii> que;
	for(int i = 0; i < N; ++i)
		for(int j = 0; j < N; ++j)
			ans[i][j] = {INF, 'X'};
	que.push({i, j}); ans[i][j] = {0, 'X'};
	while(!que.empty()) {
		auto u = que.front(); que.pop();
		// cout << u.F << ' ' << u.S << '\n';
		if(G[u.F][u.S] == 'o') {
			if(u.S + 1 < s)
				ans[u.F][u.S + 1] = {1, 'E'}, que.ep(u.F, u.S + 1);
			if(u.S - 1 >= 0)
				ans[u.F][u.S - 1] = {1, 'W'}, que.ep(u.F, u.S - 1);
			if(u.F + 1 < r)
				ans[u.F + 1][u.S] = {1, 'S'}, que.ep(u.F + 1, u.S);
			if(u.F - 1 >= 0)
				ans[u.F - 1][u.S] = {1, 'N'}, que.ep(u.F - 1, u.S);
		}
		if(G[u.F][u.S] == '>') {
			if(mkp(ans[u.F][u.S].F + 1, ans[u.F][u.S].S) < ans[u.F][u.S + 1]) {
				ans[u.F][u.S + 1] = {ans[u.F][u.S].F + 1, ans[u.F][u.S].S};
				que.ep(u.F, u.S + 1);
			}	
		}
		if(G[u.F][u.S] == '<') {
			if(mkp(ans[u.F][u.S].F + 1, ans[u.F][u.S].S) < ans[u.F][u.S - 1]) {
				ans[u.F][u.S - 1] = {ans[u.F][u.S].F + 1, ans[u.F][u.S].S};
				que.ep(u.F, u.S - 1);
			}	
		}
		if(G[u.F][u.S] == '^') {
			if(mkp(ans[u.F][u.S].F + 1, ans[u.F][u.S].S) < ans[u.F - 1][u.S]) {
				ans[u.F - 1][u.S] = {ans[u.F][u.S].F + 1, ans[u.F][u.S].S};
				que.ep(u.F - 1, u.S);
			}	
		}
		if(G[u.F][u.S] == 'v') {
			if(mkp(ans[u.F][u.S].F + 1, ans[u.F][u.S].S) < ans[u.F + 1][u.S]) {
				ans[u.F + 1][u.S] = {ans[u.F][u.S].F + 1, ans[u.F][u.S].S};
				que.ep(u.F + 1, u.S);
			}	
		}
	}
	return ans[er][es];
}

inline void solve() {
	cin >> r >> s;
	for(int i = 0; i < r; ++i)
		for(int j = 0; j < s; ++j) {
			cin >> G[i][j];
			if(G[i][j] == 'o')
				sr = i, ss = j;
			if(G[i][j] == 'x')
				er = i, es = j;
		}
	auto ret = bfs(sr, ss);
	if(ret.F == INF)
		cout << ":(";
	else
		cout << ":)\n" << ret.S << '\n';
}

int main() {
	cin.tie(0), ios::sync_with_stdio(0);
	solve();
}

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 316 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 312 KB Output is correct