제출 #910651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
910651		ByeWorld	Tracks in the Snow (BOI13_tracks)	C++14	2.19 / 100	2087 ms	220608 KiB

tracks

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define bupol __builtin_popcount
//#define int long long 
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 2e5+5;
const int MAXK = 205;
const int LOG = 20;
const int MOD = 1e9+7;
const int SQRT = 520;
const int INF = 1e9+10;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
vector <int> dx = {-1, 0, 0, 1};
vector <int> dy = {0, -1, 1, 0};

int h, w;
string s[4010];
int vis[4010][4010];

int ans, cnt, tot;
vector <pii> vec;
char fnd;
void bfs(){
    int siz = vec.size();
    for(int j=0; j<siz; j++){
        int x = vec[j].fi, y = vec[j].se;
        if(vis[x][y]==2) continue;

        bool te = 0;
        for(int i=0; i<4; i++){
            int nx = x+dx[i], ny = y+dy[i];
            if(vis[nx][ny] || s[nx][ny] == '.') continue;
            te = 1;
            if(s[nx][ny] == fnd){
                vec.pb({nx, ny});
                vis[nx][ny] = 1;
                cnt++;
            }
        }
        if(!te) vis[x][y] = 2;


        siz = vec.size();
    }
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> h >> w;
    for(int i=1; i<=h; i++){
        cin >> s[i];
        s[i] = '.'+s[i]+'.';
        for(int j=1; j<=w; j++)
            if(s[i][j]!='.') tot++;
    }
    //cout << tot << " t\n";
    for(int i=0; i<=w+1; i++){
        s[0] += '.'; s[h+1] += '.';
    }

    fnd = s[1][1]; vec.pb({1, 1}); vis[1][1] = 1; 
    cnt = 1;
    while(cnt != tot){
        ans++;
        bfs();
        // if(fnd='F'){
        //     for(auto in : vec) cout << in.fi << ' '<< in.se << " p\n";
        //     exit(0);
        // }
        if(fnd=='R') fnd = 'H';
        else fnd = 'R';
    } 
    cout << ans << '\n';
}

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