Submission #491856

#	Time	Username	Problem	Language	Result	Execution time	Memory
491856		emps	Tracks in the Snow (BOI13_tracks)	C++11	31.77 / 100	1543 ms	79024 KiB

tracks

#include <iostream>
#include <queue>
using namespace std;

int h, w;
int depth[4000][4000];
int ans = 1;
char snow[4000][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++)
	{
		for (int j = 0; j < w; j++)
		{
			cin >> snow[i][j];
			depth[i][j] = 0;
		}
	}
	
	queue<pair<int, int>> q;
	q.push({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.size() > 0)
	{
		pair<int, int> c = q.front();
		q.pop();
		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({x, y});
				}
				else
				{
					depth[x][y] = depth[c.first][c.second] + 1;
					q.push({x, y});
				}
			}
		}
	}
	cout << ans;
}

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