oj.uz

답안 #440273

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
440273 2021-07-01T21:56:37 Z penguinhacker Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 831 ms 152196 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=4000, di[4]={1, -1, 0, 0}, dj[4]={0, 0, 1, -1};
int n, m, d[mxN][mxN], ans;
string g[mxN];
bool vis[mxN][mxN];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i=0; i<n; ++i)
		cin >> g[i];
	memset(d, 0x3f, sizeof(d));
	d[0][0]=1;
	deque<ar<int, 2>> q={{0, 0}};
	while(q.size()) {
		int i=q.front()[0], j=q.front()[1];
		q.pop_front();
		if (vis[i][j])
			continue;
		vis[i][j]=1;
		ans=max(ans, d[i][j]);
		for (int k=0; k<4; ++k) {
			int ni=i+di[k], nj=j+dj[k];
			if (0<=ni&&ni<n&&0<=nj&&nj<m&&!vis[ni][nj]&&g[ni][nj]^'.') {
				if (g[i][j]==g[ni][nj]&&d[i][j]<d[ni][nj]) {
					d[ni][nj]=d[i][j];
					q.push_front({ni, nj});
				} else if (g[i][j]^g[ni][nj]&&d[i][j]+1<d[ni][nj]) {
					d[ni][nj]=d[i][j]+1;
					q.push_back({ni, nj});
				}
			}
		}
	}
	cout << ans;
	return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 65456 KB Output is correct
2 Correct 27 ms 63180 KB Output is correct
3 Correct 29 ms 63252 KB Output is correct
4 Correct 40 ms 65444 KB Output is correct
5 Correct 31 ms 64368 KB Output is correct
6 Correct 28 ms 63052 KB Output is correct
7 Correct 27 ms 63180 KB Output is correct
8 Correct 27 ms 63308 KB Output is correct
9 Correct 28 ms 63368 KB Output is correct
10 Correct 31 ms 64044 KB Output is correct
11 Correct 29 ms 63912 KB Output is correct
12 Correct 34 ms 64324 KB Output is correct
13 Correct 31 ms 64280 KB Output is correct
14 Correct 31 ms 64252 KB Output is correct
15 Correct 43 ms 65552 KB Output is correct
16 Correct 44 ms 65484 KB Output is correct
17 Correct 36 ms 65448 KB Output is correct
18 Correct 37 ms 65484 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 78032 KB Output is correct
2 Correct 74 ms 71108 KB Output is correct
3 Correct 242 ms 109136 KB Output is correct
4 Correct 93 ms 78020 KB Output is correct
5 Correct 186 ms 93336 KB Output is correct
6 Correct 831 ms 122880 KB Output is correct
7 Correct 37 ms 78660 KB Output is correct
8 Correct 37 ms 78016 KB Output is correct
9 Correct 28 ms 63268 KB Output is correct
10 Correct 28 ms 63180 KB Output is correct
11 Correct 42 ms 78372 KB Output is correct
12 Correct 29 ms 63556 KB Output is correct
13 Correct 78 ms 71060 KB Output is correct
14 Correct 54 ms 68388 KB Output is correct
15 Correct 48 ms 69012 KB Output is correct
16 Correct 48 ms 65868 KB Output is correct
17 Correct 143 ms 79184 KB Output is correct
18 Correct 103 ms 78916 KB Output is correct
19 Correct 93 ms 78040 KB Output is correct
20 Correct 92 ms 76924 KB Output is correct
21 Correct 154 ms 94276 KB Output is correct
22 Correct 181 ms 93252 KB Output is correct
23 Correct 259 ms 88816 KB Output is correct
24 Correct 153 ms 93892 KB Output is correct
25 Correct 482 ms 109224 KB Output is correct
26 Correct 458 ms 152196 KB Output is correct
27 Correct 593 ms 135832 KB Output is correct
28 Correct 828 ms 123124 KB Output is correct
29 Correct 821 ms 121144 KB Output is correct
30 Correct 733 ms 126428 KB Output is correct
31 Correct 749 ms 97220 KB Output is correct
32 Correct 536 ms 124452 KB Output is correct