Submission #137448

#	Time	Username	Problem	Language	Result	Execution time	Memory
137448		aminra	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1181 ms	114496 KiB

tracks

#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 / 30
• Subtask 2: 70 / 70