oj.uz

답안 #137448

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137448 2019-07-27T18:19:47 Z aminra Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1181 ms 114496 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)4003;
const int infint = (int)1e9 + 3;
const int MOD = (int)1e9 + 7;
const ll inf = (ll)1e18 + 3;
int deq[MAXN * MAXN], front = -1, back = 0, sze = MAXN * MAXN, n, m, xdir[4] = {-1, 0, 0, 1}, ydir[4] = {0, 1, -1, 0};
int visited[MAXN][MAXN];
char c[MAXN][MAXN];
bool full()
{
	if(front == 0 && back == sze - 1)
		return 1;
	if(front == back + 1)
		return 1;
	return 0;
}
bool empty()
{
	return front == -1;
}
void Push_front(int x)
{
	assert(!full());
	if(front == -1)
		front = 0, back = 0;
	else
	if(front == 0)
		front = sze - 1;
	else
		front--;
	deq[front] = x;
	return;
}
void Push_back(int x)
{
	assert(!full());
	if(front == -1)
		front = 0, back = 0;
	else
	if(back == sze - 1)
		back = 0;
	else
		back++;
	deq[back] = x;
}
void Pop_front() 
{ 
    assert(!empty());
    if (front == back) 
        front = -1, back = -1; 
    else
    if (front == sze -1) 
        front = 0; 
  	else
        front++;
	return; 
}
int Get_front()
{
	assert(!empty());
	return deq[front];
}
void bfs(int R, int C)
{
	visited[R][C] = 0;
	Push_front(m * R + C);
	while(!empty())
	{
		int st = Get_front();
		int x = st / m, y = st % m;
		Pop_front();
		for (int t = 0; t < 4; t++)
		{
			int nwx = x + xdir[t], nwy = y + ydir[t];
			if(0 <= nwx && nwx < n && 0 <= nwy && nwy < m && c[nwx][nwy] != '.')
			{
				if(c[x][y] != c[nwx][nwy] && visited[nwx][nwy] > visited[x][y] + 1)
					Push_back(nwx * m + nwy), visited[nwx][nwy] = visited[x][y] + 1;
				else
				if(c[x][y] == c[nwx][nwy] && visited[nwx][nwy] > visited[x][y])
					Push_front(nwx * m + nwy), visited[nwx][nwy] = visited[x][y];
			}	
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> c[i][j];
	if(c[0][0] == '.')
		return cout << 0, 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			visited[i][j] = infint;
		
	bfs(0, 0);
	int ans = -1;
	for (int i = 0; i < n; i++)	
		for (int j = 0; j < m; j++)
			if(visited[i][j] != infint)
				ans = max(ans, visited[i][j]);
	cout << ans + 1;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 5880 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 14 ms 5100 KB Output is correct
5 Correct 7 ms 3068 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 888 KB Output is correct
9 Correct 3 ms 1272 KB Output is correct
10 Correct 6 ms 2808 KB Output is correct
11 Correct 6 ms 2168 KB Output is correct
12 Correct 11 ms 3192 KB Output is correct
13 Correct 7 ms 3064 KB Output is correct
14 Correct 7 ms 3064 KB Output is correct
15 Correct 22 ms 5880 KB Output is correct
16 Correct 25 ms 5880 KB Output is correct
17 Correct 18 ms 5624 KB Output is correct
18 Correct 14 ms 5240 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 30968 KB Output is correct
2 Correct 82 ms 19296 KB Output is correct
3 Correct 498 ms 94608 KB Output is correct
4 Correct 140 ms 34812 KB Output is correct
5 Correct 300 ms 67908 KB Output is correct
6 Correct 1181 ms 106188 KB Output is correct
7 Correct 27 ms 32376 KB Output is correct
8 Correct 26 ms 30968 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 26 ms 31736 KB Output is correct
12 Correct 4 ms 1656 KB Output is correct
13 Correct 82 ms 19212 KB Output is correct
14 Correct 49 ms 12792 KB Output is correct
15 Correct 41 ms 13176 KB Output is correct
16 Correct 40 ms 7288 KB Output is correct
17 Correct 201 ms 39324 KB Output is correct
18 Correct 154 ms 35804 KB Output is correct
19 Correct 139 ms 34736 KB Output is correct
20 Correct 151 ms 31316 KB Output is correct
21 Correct 299 ms 70264 KB Output is correct
22 Correct 299 ms 68032 KB Output is correct
23 Correct 393 ms 63284 KB Output is correct
24 Correct 291 ms 69588 KB Output is correct
25 Correct 652 ms 94328 KB Output is correct
26 Correct 609 ms 104952 KB Output is correct
27 Correct 910 ms 114496 KB Output is correct
28 Correct 1130 ms 106284 KB Output is correct
29 Correct 1089 ms 106628 KB Output is correct
30 Correct 1018 ms 105156 KB Output is correct
31 Correct 951 ms 93160 KB Output is correct
32 Correct 845 ms 106104 KB Output is correct