제출 #715607

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
715607		ParsaS	Tracks in the Snow (BOI13_tracks)	C++17	97.81 / 100	932 ms	1048576 KiB

tracks

// In the name of God
//        : )
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 4000 + 5;
int di[4] = {1, -1, 0, 0}, dj[4] = {0, 0, 1, -1};
int H, W;
string grid[N];
vector<pair<int, int> > V[2];
bool vis[N][N];

bool valid(int x, int y) {
    return x >= 0 && y >= 0 && x < H && y < W && grid[x][y] != '.';
}

void dfs(int x, int y, int k) {
    V[k].pb(mp(x, y));
    vis[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int x2 = x + di[i];
        int y2 = y + dj[i];
        if (valid(x2, y2) && !vis[x2][y2] && (grid[x2][y2] == 'F') == k) {
            dfs(x2, y2, k);
        }
    }
}

void solve() {
    cin >> H >> W;
    for (int i = 0; i < H; i++)
        cin >> grid[i];
    if (grid[0][0] == '.') {
        cout << 0 << '\n';
        return;
    }
    dfs(0, 0, grid[0][0] == 'F');
    bool k = grid[0][0] == 'F';
    int ans = 0;
    while (!V[0].empty() || !V[1].empty()) {
        for (auto [x, y] : V[k]) {
            for (int i = 0; i < 4; i++) {
                int x2 = x + di[i];
                int y2 = y + dj[i];
                if (valid(x2, y2) && !vis[x2][y2]) {
                    dfs(x2, y2, grid[x2][y2] == 'F');
                }
            }
        }
        V[k].clear();
        k ^= 1;
        ans++;
    }
    cout << ans << '\n';
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

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