Submission #491859

#	Time	Username	Problem	Language	Result	Execution time	Memory
491859		emps	Tracks in the Snow (BOI13_tracks)	C++11	100 / 100	849 ms	119756 KiB

tracks

#include <iostream>
#include <string>
#include <deque>
using namespace std;

int h, w;
int depth[4000][4000];
int ans = 1;
string snow[4000];

bool inside(int x, int y)
{
	return (x > -1 && x < h && y > -1 && y < w && snow[x][y] != '.');
}

int main ()
{
	cin >> h >> w;
	for (int i = 0; i < h; i++)
	{
		cin >> snow[i];
	}
	
	for(int i = 0; i < h; i++)
	{
		for(int j = 0; j < w; j++)
		{
			depth[i][j] = 0;
		}
	}
	deque<pair<int, int>> q;
	q.push_front({0, 0});
	depth[0][0] = 1;
	
	int dx[4], dy[4];
	dx[0] = 1; dx[1] = -1; dx[2] = 0; dx[3] = 0;
	dy[0] = 0; dy[1] = 0; dy[2] = 1; dy[3] = -1;
	while(!q.empty())
	{
		pair<int, int> c = q.front();
		q.pop_front();
		ans = max(ans, depth[c.first][c.second]);
		for (int i = 0; i < 4; i++)
		{
			int x = c.first + dx[i], y = c.second + dy[i];
			if (inside(x, y) && depth[x][y] == 0)
			{
				if (snow[x][y] == snow[c.first][c.second])
				{
					depth[x][y] = depth[c.first][c.second];
					q.push_front({x, y});
				}
				else
				{
					depth[x][y] = depth[c.first][c.second] + 1;
					q.push_back({x, y});
				}
			}
		}
	}
	cout << ans;
}

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