Submission #486467

#	Time	Username	Problem	Language	Result	Execution time	Memory
486467		bill_lin	Tracks in the Snow (BOI13_tracks)	C++14	78.13 / 100	2095 ms	95208 KiB

tracks

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;

const int INF = 10000000;

int n, m;
bool is_safe(int row, int col) {
    return row >= 0 && row < n && col >= 0 && col < m;
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    
    vector<vector<char>> grid(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    vector<vector<int>> dist(n, vector<int>(m, INF));
    dist[0][0] = 1;
    queue<pii> q;
    q.push({0, 0});
    int dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0};
    while (!q.empty()) {
        int row = q.front().first, col = q.front().second;
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int dest_x = row + dx[i], dest_y = col + dy[i];
            if (is_safe(dest_x, dest_y) && grid[dest_x][dest_y] != '.') {
                int cost = dist[row][col];
                if (grid[dest_x][dest_y] != grid[row][col]) cost++;
                if (dist[dest_x][dest_y] > cost) {
                    dist[dest_x][dest_y] = cost;
                    q.push({dest_x, dest_y});
                }
            }
        }
    }
    int ans = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (dist[i][j] != INF) ans = max(ans, dist[i][j]);
        }
    }
    cout << ans << '\n';
}

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