Submission #763178

#	Time	Username	Problem	Language	Result	Execution time	Memory
763178		Kongggwp	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	735 ms	191732 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
int n , m , dx[4] = {1,0,-1,0} , dy[4] = {0,1,0,-1} , dist[4005][4005] , vis[4005][4005] , ans=1;
char grid[4005][4005];
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m;
	for(int i=0 ; i<n ; i++)for(int j=0 ; j<m ; j++)cin >> grid[i][j];
	deque<pair<int,int>>q;
	q.push_front({0,0});
	vis[0][0] = 1;
	dist[0][0] = 1;
	while(q.size())
	{
		int x = q.front().first , y = q.front().second;
		q.pop_front();
		ans = max(ans , dist[x][y]);
		for(int k=0 ; k<4 ; k++)
		{
			int xx = x + dx[k] , yy = y + dy[k];
			if(xx<0 || yy<0 || xx>=n || yy>=m || grid[xx][yy] == '.' || vis[xx][yy])continue;
			if(grid[x][y] == grid[xx][yy])
			{
				q.push_front({xx , yy});
				dist[xx][yy] = dist[x][y];
			}
			else
			{
				q.push_back({xx , yy});
				dist[xx][yy] = dist[x][y] + 1;
			}
			vis[xx][yy] = 1;
		}
	}
	cout << ans;
}

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