Submission #88707

#	Time	Username	Problem	Language	Result	Execution time	Memory
88707		popovicirobert	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	823 ms	94240 KiB

tracks

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int INF = 2e9;
const int MAXN = 4000;

char mat[MAXN + 1][MAXN + 1];

int dist[MAXN + 1][MAXN + 1];
char dl[] = {-1, 0, 1, 0}, dc[] = {0, -1, 0, 1};
int n, m;

inline bool in(int l, int c) {
    return 1 <= l && l <= n && 1 <= c && c <= m;
}

deque < pair <short, short> > deq;

inline int solve() {
    int i, j;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            dist[i][j] = INF;
        }
    }
    deq.push_back({1, 1});
    dist[1][1] = 1;
    while(deq.size()) {
        int l = deq.front().first;
        int c = deq.front().second;
        deq.pop_front();
        for(i = 0; i < 4; i++) {
            int lin = l + dl[i];
            int col = c + dc[i];
            if(in(lin, col) && mat[lin][col] != '.') {
                int cur = dist[l][c] + (mat[l][c] != mat[lin][col]);
                if(dist[lin][col] > cur) {
                    dist[lin][col] = cur;
                    if(mat[lin][col] == mat[l][c]) {
                        deq.push_front({lin, col});
                    }
                    else {
                        deq.push_back({lin, col});
                    }
                }
            }
        }
    }
    int ans = 0;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            if(mat[i][j] != '.') {
                ans = max(ans, dist[i][j]);
            }
        }
    }
    return ans;
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, j;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    int cntF = 0, cntR = 0;
    for(i = 1; i <= n; i++) {
        cin >> mat[i] + 1;
        for(j = 1; j <= m; j++) {
            if(mat[i][j] == 'R') {
                cntR++;
            }
            if(mat[i][j] == 'F') {
                cntF++;
            }
        }
    }
    if(cntF + cntR == 0) {
        cout << 0;
        return 0;
    }
    int ans = solve();
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:75:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         cin >> mat[i] + 1;
                ~~~~~~~^~~

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