Submission #885390

#	Time	Username	Problem	Language	Result	Execution time	Memory
885390		cpptowin	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1257 ms	111684 KiB

tracks

#include<bits/stdc++.h>
#define db double
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define N 5010
#define pb push_back
#define en cout<<"\n";
#define inf 1e9
#define pii pair<int,int>
#define vii vector<pii>
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(j<<1))
#define vi vector<int>
#define vvi vector<vector<int>>
#define checkfile(FiLeNaMe) { if(fopen(FiLeNaMe".inp","r")) freopen(FiLeNaMe".inp","r",stdin),freopen(FiLeNaMe".out","w",stdout); }
using namespace std;
int n,m,ans,d[N][N];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
char a[N][N];
bool safe(int i,int j)
{
	return i>0&&j>0&&i<=n&&j<=m;
}
void process()
{
	cin>>n>>m;
	fo(i,1,n) fo(j,1,m) cin>>a[i][j];
	queue<pii> q[2];
	int cur=0;//tmp queue
	d[1][1]=1;
	q[cur].push({1,1});
	while(q[0].size()||q[1].size())
	{
		int u=q[cur].front().first;
		int v=q[cur].front().second;
		q[cur].pop();
		ans=max(ans,d[u][v]);
		fo(k,0,3)
		{
			int U=u+dx[k];
			int V=v+dy[k];
			if(safe(U,V)&&a[U][V]==a[u][v]&&!d[U][V])
			{
				d[U][V]=d[u][v];
				q[cur].push({U,V});
			}
			if(safe(U,V)&&a[U][V]==('R'+'F'-a[u][v])&&!d[U][V])
			{
				d[U][V]=d[u][v]+1;
				q[1-cur].push({U,V});
			}
		}
		if(!q[cur].size()) cur^=1;
	}
	cout<<ans;
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    process();
}

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