제출 #1290299

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290299		ghammazhassan	Tracks in the Snow (BOI13_tracks)	C++20	81.25 / 100	910 ms	203636 KiB

tracks

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;
#define int long long
#define endl "\n"
#define fi first
#define se second
const int M=1e9+7;
const int inf = 1e14;
const int LOG=18;
const int N=4e3+5;
int n , m , c , w , k , t=1 , q=1 , x , y , z , l , r;
int vi[N][N];
void solve(){
    cin >> n >> m;
    string s;
    for (int i=0;i<m+2;i++){
        s+='.';
    }
    vector<string>a(n+2);
    a[0]=a[m+1]=s;
    for (int i=1;i<=n;i++){
        cin >> a[i];
        a[i]='.'+a[i];
        a[i]+='.';
    }
    for (int i=0;i<n+2;i++){
        vi[i][0]=1;
        vi[i][m+1]=1;
    }
    for (int i=0;i<m+2;i++){
        vi[0][i]=1;
        vi[n+1][i]=1;
    }
    k=0;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            k+=(a[i][j]!='.');
        }
    }
    c=0;
    int vs=0;
    vector<pair<int,int>>hl;
    hl.push_back({1,1});
    queue<pair<int,int>>o;
    char p=a[1][1];
    vector<pair<int,int>>lk;
    lk.push_back({1,0});
    lk.push_back({-1,0});
    lk.push_back({0,1});
    lk.push_back({0,-1});
    while (vs<k){
        for (auto i:hl){
            o.push(i);
            if (!vi[i.fi][i.se]){
                vs++;
                vi[i.fi][i.se]=1;
            }
        }
        hl.clear();
        while (o.size()){
            auto h=o.front();
            o.pop();
            int i=h.fi;
            int j=h.se;
            for (auto [x,y]:lk){
                if (vi[i+x][j+y])continue;
                if (a[i+x][j+y]==p){
                    vs++;
                    o.push({i+x,j+y});
            // cout << i+x << " " << j+y << endl;
                    vi[i+x][j+y]=1;
                }
                else if(a[i+x][j+y]=='.'){
                    vi[i+x][j+y]=1;
                }
                else if(hl.empty() or hl[hl.size()-1]!=make_pair(i,j)){
                    hl.push_back({i,j});
                }
            }
        }
        if (p=='R'){
            p='F';
        }
        else{
            p='R';
        }
        c++;
        // cout << endl;
        // for (auto i:hl){
        //     cout << i.fi << " " << i.se << endl;
        // }
        // cout << vs;
        // cout << endl;    
    }
    cout << c << endl;
}
signed main()    
{   

    ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
    cin.tie(0), cout.tie(0);//DO NOT USE IN INTERACTIVE
    cout << fixed << setprecision(9);
    srand(time(0));
    // int t=1;
    // cin >> t;
    for (int _=1;_<=t;_++){
        solve();
        q++;
    }
} 

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