Submission #680043

#	Time	Username	Problem	Language	Result	Execution time	Memory
680043		hanlulu	Tracks in the Snow (BOI13_tracks)	C++14	0 / 100	1464 ms	110648 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
int xdir[4] = {0,0,1,-1};
int ydir[4] = {1,-1,0,0};
int main() {
	int  n,m;
	cin >> n >> m;
	vector<vector<char>> grid(n,vector<char>(m));
	for (int i = 0; i < n; i++)
	for (int j = 0; j < m; j++)
		cin >> grid[i][j];
	vector<vector<int>> dis(n,vector<int>(m,-1));
	deque<pair<int,int>> myq;
	myq.push_front({0,0});
	dis[0][0] = 0;
	int ans = 0;
	while (!myq.empty()) 
	{
		pair<int,int> u = myq.front();
		myq.pop_front();
		ans = max(ans, dis[u.first][u.second]);
		for (int i = 0; i < 4; i++)
		{
			int x = u.first + xdir[i];
			int y = u.second + ydir[i];
			if (x < 0 || x == n || y < 0 || y == m || dis[x][y] != -1 || grid[x][y] == '.') continue;
			if (grid[x][y] == grid[u.first][u.second]) 
			{
				dis[x][y] = dis[u.first][u.second];
				myq.push_front({x,y});	
			}
			else
			{
				dis[x][y] = dis[u.first][u.second] + 1;
				myq.push_back({x,y});
			}	
		}	
	}

	cout << ans << '\n';	
	return 0;
}

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