Submission #1129337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129337		subham_krr	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1378 ms	222732 KiB

tracks

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

signed main() {
    int n, m;
    cin >> n >> m;

    int r = 0, f = 0;
    vector<vector<char> > g(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
            if (g[i][j] == 'R') {
                r++;
            } else if (g[i][j] == 'F') {
                f++;
            }
        }
    }

    // Define direction vectors for 4 directions
   	vector<pair<int,int > >v;
	v.push_back({-1,0});
		v.push_back({0,-1});
		v.push_back({0,1});
		v.push_back({1,0});

    // Initialize the level array
    vector<vector<int> > level(n, vector<int>(m, LLONG_MAX));
    level[0][0] = 1;

    // 0/1 BFS using deque
    deque<pair<int, int> > dq;
    dq.push_front({0, 0});
int ans=0;
    while (!dq.empty()) {
        pair<int, int> p = dq.front();
        dq.pop_front();
        ans=max(ans,level[p.first][p.second]);

        for (int i = 0; i < 4; i++) {
            int d = p.first + v[i].first;
            int e = p.second + v[i].second;

            // Boundary check
            if (d >= 0 && d < n && e >= 0 && e < m && g[d][e]!='.') {
                int wt = (g[p.first][p.second] != g[d][e]) ? 1 : 0;
                
                if (wt + level[p.first][p.second] < level[d][e]) {
                    level[d][e] = wt + level[p.first][p.second];
                    if (wt == 1) {
                        dq.push_back({d, e}); // Push to the back if weight is 1
                    } else {
                        dq.push_front({d, e}); // Push to the front if weight is 0
                    }
                }
            }
        }
    }
cout<<ans<<endl;
    // Adjust result for corner cases
//    int result = level[n-1][m-1];
//    if (result == LLONG_MAX) {
//        cout << -1 << endl; // If destination is unreachable
//    } else {
//        cout << result  << endl; // Include additional penalties if required
//    }

    return 0;
}

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