oj.uz

답안 #767704

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
767704 2023-06-27T05:07:15 Z lukehsiao Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 486 ms 130692 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN = 4000, INF = 2e9;

int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};

int H, W, depth[mxN][mxN];
string grid[mxN];

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

	cin >> H >> W;
	for (int i=0; i<H; ++i)
		cin >> grid[i];
	
	deque<pair<int, int>> dq;
	dq.push_front({0, 0});
	depth[0][0] = 1;
	
	int ans = 0;
	while (!dq.empty()) {
		int r = dq.front().first;
		int c = dq.front().second;
		dq.pop_front();

		ans = max(ans, depth[r][c]);

		for (int i=0; i<4; ++i) {
			int nr = r + dx[i], nc = c + dy[i];
			if (nr >= 0 && nr < H && nc >= 0 && nc < W &&
					grid[nr][nc] != '.' && depth[nr][nc] == 0) {
				if (grid[r][c] == grid[nr][nc]) {
					depth[nr][nc] = depth[r][c];
					dq.push_front({nr, nc});
				} else {
					depth[nr][nc] = depth[r][c] + 1;
					dq.push_back({nr, nc});
				}
			}
		}
	}

	cout << ans << '\n';
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 3924 KB Output is correct
2 Correct 1 ms 452 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 6 ms 3540 KB Output is correct
5 Correct 2 ms 2016 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 3 ms 1676 KB Output is correct
11 Correct 2 ms 1492 KB Output is correct
12 Correct 4 ms 2176 KB Output is correct
13 Correct 2 ms 2004 KB Output is correct
14 Correct 2 ms 2004 KB Output is correct
15 Correct 8 ms 3668 KB Output is correct
16 Correct 10 ms 3928 KB Output is correct
17 Correct 7 ms 3696 KB Output is correct
18 Correct 6 ms 3540 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16172 KB Output is correct
2 Correct 30 ms 10548 KB Output is correct
3 Correct 170 ms 60088 KB Output is correct
4 Correct 66 ms 25944 KB Output is correct
5 Correct 88 ms 42888 KB Output is correct
6 Correct 480 ms 94640 KB Output is correct
7 Correct 10 ms 16980 KB Output is correct
8 Correct 9 ms 16212 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 9 ms 16364 KB Output is correct
12 Correct 2 ms 1108 KB Output is correct
13 Correct 30 ms 10512 KB Output is correct
14 Correct 18 ms 7280 KB Output is correct
15 Correct 13 ms 9548 KB Output is correct
16 Correct 14 ms 4608 KB Output is correct
17 Correct 83 ms 21508 KB Output is correct
18 Correct 57 ms 28616 KB Output is correct
19 Correct 52 ms 25952 KB Output is correct
20 Correct 39 ms 19176 KB Output is correct
21 Correct 94 ms 42072 KB Output is correct
22 Correct 105 ms 42940 KB Output is correct
23 Correct 142 ms 35080 KB Output is correct
24 Correct 99 ms 38956 KB Output is correct
25 Correct 302 ms 81044 KB Output is correct
26 Correct 336 ms 130692 KB Output is correct
27 Correct 396 ms 107228 KB Output is correct
28 Correct 486 ms 94312 KB Output is correct
29 Correct 470 ms 92588 KB Output is correct
30 Correct 468 ms 96992 KB Output is correct
31 Correct 333 ms 62032 KB Output is correct
32 Correct 353 ms 92580 KB Output is correct