oj.uz

답안 #369241

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
369241 2021-02-21T01:46:49 Z vm152 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 633 ms 123900 KB 
#include <bits/stdc++.h>
using namespace std ;

#define ios ios_base::sync_with_stdio(0); cin.tie(0) ; cout.tie(0)
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define endl '\n'

typedef long long int ll ;
typedef long double lb ;
typedef unsigned long long int ul ;
const ll MOD = 1e9 + 7 ;

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

void solve(){
	 int h, w ;
	 cin >> h >> w ;
	 string s[h] ;
	 for (int i = 0; i < h; i++) cin >> s[i] ;
	 deque<pair<int, int>> q ;
	 int dist[h][w] ;
	 for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) dist[i][j] = 0 ;
	 int ans = 0 ;
	 q.push_back({0, 0}) ;
	 dist[0][0] = 1 ;
	 while (!q.empty()) {
	 	 pair<int, int> c = q.front() ;
	 	 q.pop_front() ;
	 	 ans = max(ans, dist[c.f][c.s]) ;
	 	 for (int i = 0; i < 4; i++) {
			 int x = c.f + dx[i]; int y = c.s + dy[i] ;
			 if (x < 0 || x >= h || y < 0 || y >= w || s[x][y] == '.') continue ;
			 if (dist[x][y] == 0) {
			 	 if (s[x][y] == s[c.f][c.s]) {
			 	 	 dist[x][y] = dist[c.f][c.s] ;
				 	 q.push_front({x, y}) ;
				 }
				 else {
				 	 dist[x][y] = dist[c.f][c.s] + 1 ;
				 	 q.push_back({x, y}) ;
				 }
			 }
		 }
	 }
	 cout << ans << endl ;
}

int main(){
	 ios ;
	 solve() ;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1900 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 6 ms 1516 KB Output is correct
5 Correct 2 ms 876 KB Output is correct
6 Correct 3 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 4 ms 876 KB Output is correct
13 Correct 3 ms 876 KB Output is correct
14 Correct 2 ms 876 KB Output is correct
15 Correct 11 ms 2048 KB Output is correct
16 Correct 11 ms 1900 KB Output is correct
17 Correct 8 ms 1772 KB Output is correct
18 Correct 6 ms 1516 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 38 ms 9708 KB Output is correct
3 Correct 228 ms 96276 KB Output is correct
4 Correct 63 ms 22636 KB Output is correct
5 Correct 172 ms 54380 KB Output is correct
6 Correct 622 ms 109648 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 38 ms 9708 KB Output is correct
14 Correct 21 ms 5740 KB Output is correct
15 Correct 18 ms 6380 KB Output is correct
16 Correct 18 ms 4204 KB Output is correct
17 Correct 102 ms 24684 KB Output is correct
18 Correct 95 ms 24172 KB Output is correct
19 Correct 65 ms 22636 KB Output is correct
20 Correct 50 ms 20844 KB Output is correct
21 Correct 126 ms 56044 KB Output is correct
22 Correct 166 ms 54380 KB Output is correct
23 Correct 204 ms 46700 KB Output is correct
24 Correct 131 ms 54636 KB Output is correct
25 Correct 501 ms 96512 KB Output is correct
26 Correct 353 ms 123900 KB Output is correct
27 Correct 472 ms 114128 KB Output is correct
28 Correct 607 ms 109640 KB Output is correct
29 Correct 633 ms 110072 KB Output is correct
30 Correct 547 ms 109040 KB Output is correct
31 Correct 524 ms 62092 KB Output is correct
32 Correct 456 ms 112036 KB Output is correct