제출 #1207153

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1207153		andrejikus	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	541 ms	228512 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); }
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)

const int N = 4003;
char a[N][N];
bool vis[N][N];
const int POM[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

void solve() {
    int n, m; cin >> n >> m;
    deque<tuple<int, int, int, char>> pq;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> a[i][j];

    pq.push_back({1, n, m, a[n][m]});
    int ans = 1;

    while (!pq.empty()) {
        auto [w, i, j, c] = pq.front(); pq.pop_front();
        if (vis[i][j]) continue;
        ans = max(ans, w);
        vis[i][j] = true;
        for (int d = 0; d < 4; d++) {
            int ik = i + POM[d][0], jk = j + POM[d][1];
            if (ik < 1 || ik > n || jk < 1 || jk > m) continue;
            if (vis[ik][jk] || a[ik][jk] == '.') continue;
            char c2 = a[ik][jk];
            if (c != c2)
                pq.push_back({w + 1, ik, jk, c2});
            else
                pq.push_front({w, ik, jk, c2});
        }
    }

    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
	int t=1; //cin >> t;
	while (t--) {
        solve();
	}
}

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