답안 #69494

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
69494 2018-08-21T03:50:25 Z MatheusLealV Tracks in the Snow (BOI13_tracks) C++17
100 / 100
1389 ms 502976 KB
#include <bits/stdc++.h>
#define N 4003
#define NN 16000002
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, m, ans, cnt, dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

int dist[N][N];

char mat[N][N], T;

vector<int> grafo[NN];

int bfs01()
{
	deque < pii > bfs;

	bfs.push_back({1, 1});

	memset(dist, 0x3f3f3f3f, sizeof dist);

	dist[1][1] = 1;

	while(!bfs.empty())
	{
		int x = bfs.front().f, y = bfs.front().s;

		bfs.pop_front();

		ans = max(ans, dist[x][y]);

		for(int p = 0; p < 4; p++)
		{
			int a = x + dx[p], b = y + dy[p];

			if(!a or !b or a > n or b > m or mat[a][b] == '.') continue;

			int custo = (mat[a][b] == mat[x][y] ? 0 : 1);

			if(dist[a][b] > dist[x][y] + custo)
			{
				dist[a][b] = dist[x][y] + custo;

				if(!custo) bfs.push_front({a, b});

				else bfs.push_back({a, b});
			} 
		}
	}

	return ans;
}

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

	cin>>n>>m;

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++) cin>>mat[i][j];

	cout<<bfs01()<<"\n";
}
# 결과 실행 시간 메모리 Grader output
1 Correct 465 ms 440816 KB Output is correct
2 Correct 418 ms 440816 KB Output is correct
3 Correct 387 ms 440816 KB Output is correct
4 Correct 395 ms 441216 KB Output is correct
5 Correct 430 ms 441216 KB Output is correct
6 Correct 452 ms 441216 KB Output is correct
7 Correct 391 ms 441216 KB Output is correct
8 Correct 366 ms 441216 KB Output is correct
9 Correct 389 ms 441216 KB Output is correct
10 Correct 383 ms 441216 KB Output is correct
11 Correct 371 ms 441216 KB Output is correct
12 Correct 388 ms 441216 KB Output is correct
13 Correct 380 ms 441216 KB Output is correct
14 Correct 384 ms 441216 KB Output is correct
15 Correct 440 ms 441216 KB Output is correct
16 Correct 451 ms 441216 KB Output is correct
17 Correct 405 ms 441216 KB Output is correct
18 Correct 449 ms 441216 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 426 ms 453996 KB Output is correct
2 Correct 439 ms 453996 KB Output is correct
3 Correct 768 ms 454784 KB Output is correct
4 Correct 501 ms 454784 KB Output is correct
5 Correct 633 ms 454784 KB Output is correct
6 Correct 1310 ms 468072 KB Output is correct
7 Correct 393 ms 468072 KB Output is correct
8 Correct 396 ms 468072 KB Output is correct
9 Correct 392 ms 468072 KB Output is correct
10 Correct 383 ms 468072 KB Output is correct
11 Correct 393 ms 468072 KB Output is correct
12 Correct 457 ms 468072 KB Output is correct
13 Correct 503 ms 468072 KB Output is correct
14 Correct 483 ms 468072 KB Output is correct
15 Correct 421 ms 468072 KB Output is correct
16 Correct 402 ms 468072 KB Output is correct
17 Correct 655 ms 468072 KB Output is correct
18 Correct 516 ms 468072 KB Output is correct
19 Correct 511 ms 468072 KB Output is correct
20 Correct 477 ms 468072 KB Output is correct
21 Correct 586 ms 468072 KB Output is correct
22 Correct 678 ms 468072 KB Output is correct
23 Correct 686 ms 468072 KB Output is correct
24 Correct 672 ms 468072 KB Output is correct
25 Correct 1047 ms 468072 KB Output is correct
26 Correct 1389 ms 502976 KB Output is correct
27 Correct 1340 ms 502976 KB Output is correct
28 Correct 1335 ms 502976 KB Output is correct
29 Correct 1230 ms 502976 KB Output is correct
30 Correct 1231 ms 502976 KB Output is correct
31 Correct 1062 ms 502976 KB Output is correct
32 Correct 1188 ms 502976 KB Output is correct