Submission #111805

#	Time	Username	Problem	Language	Result	Execution time	Memory
111805		anayk	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1271 ms	176188 KiB

tracks

#include <iostream>
#include <vector>
#include <deque>

#define MAXN 4005
#define MAXV 17000000

int n, m;
std::deque<std::pair<int, int> > bfs;
bool vis[MAXN][MAXN];
int d[MAXN][MAXN];
//std::vector<std::pair<int, bool> > Adj[MAXV];
int mat[MAXN][MAXN];

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin >> n >> m;
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			char c;
			std::cin >> c;
			if(c == 'R')
				mat[i][j] = 1;
			else if(c == 'F')
				mat[i][j] = 2;
			else
				mat[i][j] = 0;
		}
	}
	
	bfs.push_front({0, 0});
	d[0][0] = 0;
	vis[0][0] = true;
	
	int dx[] = {1, 0, -1, 0};
	int dy[] = {0, 1, 0, -1};
	
	int answer = 0;
	while(!bfs.empty())
	{
		std::pair<int, int> u = bfs.front();
		bfs.pop_front();
		int i = u.first;
		int j = u.second;

		for(int k = 0; k < 4; k++)
		{
			int p = i + dx[k];
			int q = j + dy[k];
			
			if(p < 0 || p >= n || q < 0 || q >= m)
				continue;
			
			if(!vis[p][q] && mat[p][q])
			{
				vis[p][q] = true;
				bool type = (mat[p][q] != mat[i][j]);
				d[p][q] = d[i][j];
				if(type)
				{
					d[p][q]++;
					bfs.push_back({p, q});
				}
				else
					bfs.push_front({p, q});
				answer = std::max(answer, d[p][q]);
			}
		}
	}
	
	std::cout << answer+1 << std::endl;
	
	return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70