Submission #378377

#	Time	Username	Problem	Language	Result	Execution time	Memory
378377		YJU	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	950 ms	78856 KiB

tracks

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef int ll;
typedef pair<ll,ll> pll;
#define X first
#define Y second
#define mp make_pair
#define REP1(i,n) for(int i=1;i<=n;i++)
const ll N=4e3+5;

string grid[N];
bool vis[N][N];
queue<pll> que;
ll n,m,ans;

ll dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

pll dest(pll now,ll dir){
	return mp(now.X+dx[dir],now.Y+dy[dir]);
}

bool invalid(pll now){
	return (now.X<=0||now.X>n||now.Y<=0||now.Y>m);
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	REP1(i,n)cin>>grid[i],grid[i]='.'+grid[i]+'.';
	que.push(mp(1,1));vis[1][1]=1;
	que.push(mp(n,m));vis[n][m]=1;
	for(char i=grid[1][1];;i=(i=='F'?'R':'F')){
		vector<pll> nxt;
		++ans;
		while(!(que.empty())){
            pll nd=que.front();que.pop();
            for(int j=0;j<4;j++){
				pll to=dest(nd,j);
				if(vis[to.X][to.Y]||invalid(to))continue;
				if(grid[to.X][to.Y]==i){
					vis[to.X][to.Y]=1;
					que.push(to);
				}else if(grid[to.X][to.Y]!='.'){
					vis[to.X][to.Y]=1;
                    nxt.push_back(to);
				}
            }
		}
		if((ll)nxt.size()==0)break;
		for(pll j:nxt)que.push(j);
	}
	cout<<ans<<"\n";
	return 0;
}

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