oj.uz

답안 #340530

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
340530 2020-12-27T20:32:29 Z rqi Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1715 ms 151552 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;

#define mp make_pair
#define f first
#define s second

#define sz(x) (int)(x).size()

int xd[4] = {1, 0, -1, 0};
int yd[4] = {0, 1, 0, -1};

const int MOD = 1e9+7;

int grid[4005][4005];
int dist[4005][4005];

int ans = 1;

int main(){
	int H, W;
	cin >> H >> W;
	for(int i = 1; i <= H; i++){
		string s;
		cin >> s;
		for(int j = 0; j < W; j++){
			if(s[j] == 'R'){
				grid[i][j+1] = 1;
			}
			else if(s[j] == 'F'){
				grid[i][j+1] = 2;
			}
		}
	}

	for(int i = 1; i <= H; i++){
		for(int j = 1; j <= W; j++){
			dist[i][j] = MOD;
		}
	}

	
	queue<pi> q; //have ans value
	queue<pi> nq;

	dist[1][1] = 1;
	q.push(mp(1, 1));

	while(sz(q)){
		pi co = q.front();
		q.pop();

		//cout << co.f << " " << co.s << "\n";

		for(int d = 0; d < 4; d++){
			int x = co.f+xd[d];
			int y = co.s+yd[d];

			

			if(grid[x][y] == 0) continue;

			if(dist[x][y] != MOD) continue;

			//cout << "x y: " << x << " " << y << "\n";

			if(grid[x][y] == grid[co.f][co.s]){
				dist[x][y] = ans;
				q.push(mp(x, y));
			}
			else{
				dist[x][y] = ans+1;
				nq.push(mp(x, y));
			}
		}

		if(sz(q) == 0){
			if(sz(nq) == 0) break;
			swap(nq, q);
			//cout << "AD" << "\n";
			ans++;
		}
	}


	cout << ans << "\n";

}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 6380 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 13 ms 5740 KB Output is correct
5 Correct 6 ms 3308 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 896 KB Output is correct
9 Correct 1 ms 1260 KB Output is correct
10 Correct 5 ms 2796 KB Output is correct
11 Correct 4 ms 2284 KB Output is correct
12 Correct 9 ms 3436 KB Output is correct
13 Correct 5 ms 3308 KB Output is correct
14 Correct 6 ms 3308 KB Output is correct
15 Correct 19 ms 6380 KB Output is correct
16 Correct 22 ms 6396 KB Output is correct
17 Correct 21 ms 6252 KB Output is correct
18 Correct 13 ms 5760 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 31468 KB Output is correct
2 Correct 97 ms 21356 KB Output is correct
3 Correct 631 ms 120556 KB Output is correct
4 Correct 171 ms 47540 KB Output is correct
5 Correct 372 ms 88816 KB Output is correct
6 Correct 1715 ms 151520 KB Output is correct
7 Correct 19 ms 32876 KB Output is correct
8 Correct 18 ms 31468 KB Output is correct
9 Correct 4 ms 876 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 19 ms 32236 KB Output is correct
12 Correct 2 ms 1772 KB Output is correct
13 Correct 96 ms 21440 KB Output is correct
14 Correct 53 ms 14060 KB Output is correct
15 Correct 52 ms 17132 KB Output is correct
16 Correct 39 ms 8300 KB Output is correct
17 Correct 245 ms 44908 KB Output is correct
18 Correct 190 ms 51564 KB Output is correct
19 Correct 172 ms 47468 KB Output is correct
20 Correct 139 ms 39276 KB Output is correct
21 Correct 352 ms 89068 KB Output is correct
22 Correct 373 ms 88684 KB Output is correct
23 Correct 479 ms 73324 KB Output is correct
24 Correct 350 ms 85760 KB Output is correct
25 Correct 835 ms 141420 KB Output is correct
26 Correct 987 ms 122092 KB Output is correct
27 Correct 1321 ms 143144 KB Output is correct
28 Correct 1670 ms 151552 KB Output is correct
29 Correct 1602 ms 150244 KB Output is correct
30 Correct 1530 ms 146428 KB Output is correct
31 Correct 1168 ms 111388 KB Output is correct
32 Correct 1207 ms 142316 KB Output is correct