Submission #1180929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180929		boclobanchat	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	852 ms	96088 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
const int MAXN=4444;
int dp[MAXN][MAXN];
queue<ii> Q[2];
string s[MAXN];
int n,m,cc=0;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ca=0,cb=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
		cin>>s[i];
		s[i]=' '+s[i];
		for(auto v:s[i]) ca+=(v=='R'),cb+=(v=='F');
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) dp[i][j]=1e9;
	dp[1][1]=1,Q[1].push({1,1});
	int ans=0;
	for(int i=1;;i++)
	{
		int za=i%2,zb=1-i%2;
		if(Q[za].empty())
		{
			ans=i;
			break;
		}
		while(!Q[za].empty())
		{
			int a=Q[za].front().fi,b=Q[za].front().se;
			Q[za].pop();
			if(dp[a][b]<i) continue;
			for(int j=0;j<4;j++)
			{
				int x=a+dx[j],y=b+dy[j];
				if(dp[x][y]>i+(s[x][y]!=s[a][b])&&x>=1&&x<=n&&y>=1&&y<=m&&s[x][y]!='.') Q[(dp[x][y]=i+(s[x][y]!=s[a][b]))%2].push({x,y});
			}
		}
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ca-=(s[i][j]=='R'&&dp[i][j]!=1e9),cb-=(s[i][j]=='F'&&dp[i][j]!=1e9);
	cout<<ans-1;
}

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