Submission #698857

#	Time	Username	Problem	Language	Result	Execution time	Memory
698857		Azther0z	Tracks in the Snow (BOI13_tracks)	C++11	100 / 100	927 ms	130980 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
int n,m;
char grid[4001][4001];
int dist[4001][4001];
int di[]={0,0,1,-1};
int dj[]={1,-1,0,0};
int result=0;
bool valid(int i,int j)
{
	return 0<=i&&i<n&&0<=j&&j<m&&grid[i][j]!='.'&&dist[i][j]==0;
}
void bfs(int i,int j)
{
	deque<pair<int,int>> dq;
	dq.push_front({i,j});
	dist[i][j]=1;
	while(!dq.empty())
	{
		int ci=dq.front().first;
		int cj=dq.front().second;
		dq.pop_front();
		result=max(result,dist[ci][cj]);
		for(int k=0;k<4;k++)
		{
			int ni=ci+di[k];
			int nj=cj+dj[k];
			if(valid(ni,nj))
			{
				if(grid[ci][cj]==grid[ni][nj])
				{
					dq.push_front({ni,nj});
					dist[ni][nj]=dist[ci][cj];
				}
				else
				{
					dq.push_back({ni,nj});
					dist[ni][nj]=dist[ci][cj]+1;
				}
			}
		}
	}
}
int main()
{
	cin >> n >> m;
	for(int i=0;i<n;i++)
		cin >> grid[i];
	bfs(0,0);
	cout << result;
}

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