제출 #1313552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313552		shirokito	Tracks in the Snow (BOI13_tracks)	C++20	47.50 / 100	2134 ms	1114112 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

#define ForUp(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define ForDn(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define all(a) (a).begin(), (a).end()

using ll = long long;

const int N = 4000 + 24;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

int n, m; char a[N][N]; bool vis[N][N];
int cnt_visit;

bool inside(int i, int j) {
    return (i >= 1 && i <= n && j >= 1 && j <= m);
}

void dfs(char c, int u, int v) {
    a[u][v] = (a[u][v] == 'F' ? 'R' : 'F');
    cnt_visit++; vis[u][v] = 1;

    ForUp (_, 0, 3) {
        int i = u + dx[_], j = v + dy[_];
        if (!vis[i][j] && inside(i, j) && a[i][j] == c) {
            dfs(c, i, j);
        }   
    }
}

void solve() {
    cin >> n >> m;
    int cnt_all = 0;

    ForUp (i, 1, n) ForUp (j, 1, m) {
        cin >> a[i][j];
        cnt_all += (a[i][j] != '.');
    }

    int res = 0;

    while (true) {
        ForUp (i, 1, n) ForUp (j, 1, m) vis[i][j] = 0;

        cnt_visit = 0; dfs(a[1][1], 1, 1);
        res++;
        
        if (cnt_visit == cnt_all) break;
    }

    cout << res << '\n';
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);

    int T = 1; // cin >> T;
    while (T--) {
        solve();
    }
}

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