Submission #842602

#	Time	Username	Problem	Language	Result	Execution time	Memory
842602		Qang	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	423 ms	118852 KiB

tracks

#include <bits/stdc++.h> // 0/1 BFS
using namespace std;
#define MAXN 4001
string g[MAXN];
int n, m, depth[MAXN][MAXN], dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 }; 

bool inside(int i, int j) {
    return i >= 0 && i < n && j >= 0 && j < m && g[i][j] != '.';
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        cin >> g[i];
    depth[0][0] = 1; //depth[i][j] = 0 means unvisited
    deque<pair<int, int>> q;
    q.push_back({ 0, 0 });
    int ans = 1;
    while (!q.empty()) {
        auto z = q.front();
        q.pop_front();
        ans = max(ans, depth[z.first][z.second]);
        for (int i = 0; i < 4; ++i) {
            int f = z.first + dx[i], s = z.second + dy[i];
            if (inside(f, s) && depth[f][s] == 0) {
                if (g[f][s] == g[z.first][z.second]) {
                    depth[f][s] = depth[z.first][z.second];
                    q.push_front({ f, s });
                }
                else {
                    depth[f][s] = depth[z.first][z.second] + 1;
                    q.push_back({ f, s });
                }
            }
        }
    }
    cout << ans;
}

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