Submission #1120513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120513		vjudge1	Tracks in the Snow (BOI13_tracks)	C++14	93.44 / 100	2100 ms	593896 KiB

tracks

#pragma GCC optimize ("O1")
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define pb push_back
#define F first
#define S second
#define ll long long
#define int ll
#define pii pair<int, int>
#define io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define M_PI 3.14159265358979323846
#define all(v) v.begin(), v.end()
#define pss pair<string, string>
#define no cout<<"NO"<<endl;
#define yes cout<<"YES"<<endl;
#define imp cout<<-1<<endl;
#define flu cout.flush();
#define Endl endl

const int N = 100009;
const int mod = 1e9+7;

int a[4005][4005];
int used[4005][4005];
int dx[]={1, -1, 0, 0, 1, -1, 1, -1};
int dy[]={0, 0, -1, 1, 1, -1, -1, 1};
int n, m;
int start, ans=1, cnt=0;

vector<pii>ne;
queue<pii>q;

void bfs(){
    while(!q.empty()){
        int x=q.front().F, y=q.front().S;
        q.pop();
        /*cout<<x<<" "<<y<<endl;
            cnt++;
        if(cnt>50){
            exit(0);
        }*/
        if(used[x][y]!=0){
            continue;
        }
        used[x][y]++;
        for(int i=0; i<4; i++){
            int xx=dx[i]+x, yy=dy[i]+y;
            if(xx>=n or xx<0){
                continue;
            }
            if(yy>=m or yy<0){
                continue;
            }
            if(used[xx][yy]==0 and a[xx][yy]==start){
                q.push({xx, yy});
            }
            if(used[xx][yy]==0 and a[xx][yy]==(-1)*start){
                ne.pb({xx, yy});
            }
        }
    }
    if(ne.size()!=0){
        ans++;
        start*=(-1);
        for(pii i : ne){
            q.push({i.F, i.S});
        }
        ne.clear();
        bfs();
    }

}

void solve(){
    cin>>n>>m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            char c;
            cin>>c;
            if(c=='F'){
                a[i][j]=1;
            }
            else if(c=='R'){
                a[i][j]=-1;
            }
        }
    }
    start=a[0][0];
    q.push({0, 0});
    bfs();
    cout<<ans<<endl;
/*

FRFF
FRRR
FFFF

FFRFFFFF
FFRRRFFF
FFFFFFFF
FFRRRFFR
FFFFFFFF

*/
}

signed main(){
    //io;
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

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