oj.uz

답안 #860637

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
860637 2023-10-13T15:05:46 Z serifefedartar Patkice II (COCI21_patkice2) C++17
110 / 110
 720 ms 375232 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 18; 
const ll MAXN = 1e5 + 100;

vector<pair<int,pair<int,int>>> graph[2005][2005];
string grid[2005];
int dist[2005][2005];
pair<int,int> s, e, from[2005][2005];
void change(int row, int col, int nrow, int ncol) {
	if (nrow > row)
		grid[row][col] = 'v';
	else if (nrow < row)
		grid[row][col] = '^';
	else if (ncol < col)
		grid[row][col] = '<';
	else
		grid[row][col] = '>'; 
}

int r, c;
bool check(int row, int col) {
	if (row >= 0 && col >= 0 && r > row && c > col)
		return true;
	return false;
}

int main() {
	fast
	cin >> r >> c;

	for (int i = 0; i < 2005; i++) {
		for (int j = 0; j < 2005; j++)
			dist[i][j] = 1e8;
	}

	for (int i = 0; i < r; i++)
		cin >> grid[i];

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (grid[i][j] == '>') {
			    if (check(i, j+1))
				    graph[i][j].push_back({0, {i, j+1}});
				if (check(i+1, j))
				    graph[i][j].push_back({1, {i+1, j}});
				if (check(i, j-1))
				    graph[i][j].push_back({1, {i, j-1}});
				if (check(i-1, j))
					graph[i][j].push_back({1, {i-1, j}});
			} else if (grid[i][j] == '<') {
				if (check(i, j+1))
					graph[i][j].push_back({1, {i, j+1}});
				if (check(i+1, j))
					graph[i][j].push_back({1, {i+1, j}});
				if (check(i, j-1))
					graph[i][j].push_back({0, {i, j-1}});
				if (check(i-1, j))
					graph[i][j].push_back({1, {i-1, j}});
			} else if (grid[i][j] == 'v') {
				if (check(i, j+1))
					graph[i][j].push_back({1, {i, j+1}});
				if (check(i+1, j))
					graph[i][j].push_back({0, {i+1, j}});
				if (check(i, j-1))
					graph[i][j].push_back({1, {i, j-1}});
				if (check(i-1, j))
					graph[i][j].push_back({1, {i-1, j}});
			} else if (grid[i][j] == '^') {
				if (check(i, j+1))
					graph[i][j].push_back({1, {i, j+1}});
				if (check(i+1, j))
					graph[i][j].push_back({1, {i+1, j}});
				if (check(i, j-1))
					graph[i][j].push_back({1, {i, j-1}});
				if (check(i-1, j))
					graph[i][j].push_back({0, {i-1, j}});
			} else if (grid[i][j] == '.') {
				if (check(i, j+1))
					graph[i][j].push_back({1, {i, j+1}});
				if (check(i+1, j))
					graph[i][j].push_back({1, {i+1, j}});
				if (check(i, j-1))
					graph[i][j].push_back({1, {i, j-1}});
				if (check(i-1, j))
					graph[i][j].push_back({1, {i-1, j}});
			} else if (grid[i][j] == 'o') {
				s = {i, j};
				if (check(i, j+1))
					graph[i][j].push_back({0, {i, j+1}});
				if (check(i+1, j))
					graph[i][j].push_back({0, {i+1, j}});
				if (check(i, j-1))
					graph[i][j].push_back({0, {i, j-1}});
				if (check(i-1, j))
					graph[i][j].push_back({0, {i-1, j}});
			} else
				e = {i, j};
		} 
	}

	deque<pair<int,int>> dq;
	dq.push_back(s);
	dist[s.f][s.s] = 0;
	while (!dq.empty()) {
		int row = dq.front().f;
		int col = dq.front().s;
		dq.pop_front();

		for (auto u : graph[row][col]) {
			int w = u.f;
			int nrow = u.s.f;
			int ncol = u.s.s;
			if (dist[nrow][ncol] > w + dist[row][col]) {
				from[nrow][ncol] = {row, col};
				dist[nrow][ncol] = w + dist[row][col];
				if (w == 1)
					dq.push_back({nrow, ncol});
				else
					dq.push_front({nrow, ncol});
			}
		}
	}

	cout << dist[e.f][e.s] << "\n";
	pair<int,int> now = from[e.f][e.s];
	pair<int,int> last = e;
	while (now != s) {
		change(now.f, now.s, last.f, last.s);
		now = from[now.f][now.s];
		last = from[last.f][last.s];
	}

	for (int i = 0; i < r; i++)
		cout << grid[i] << "\n";
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 111196 KB Output is correct
2 Correct 25 ms 111200 KB Output is correct
3 Correct 24 ms 113244 KB Output is correct
4 Correct 25 ms 113244 KB Output is correct
5 Correct 23 ms 110940 KB Output is correct

Subtask #2
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 111196 KB Output is correct
2 Correct 25 ms 111200 KB Output is correct
3 Correct 24 ms 113244 KB Output is correct
4 Correct 25 ms 113244 KB Output is correct
5 Correct 23 ms 110940 KB Output is correct
6 Correct 107 ms 153848 KB Output is correct
7 Correct 127 ms 160080 KB Output is correct
8 Correct 238 ms 213712 KB Output is correct
9 Correct 434 ms 275452 KB Output is correct
10 Correct 531 ms 343968 KB Output is correct
11 Correct 720 ms 375232 KB Output is correct