Submission #1129330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129330		subham_krr	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	2101 ms	142424 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 = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	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] = 0;

    // BFS queue
    queue<pair<int, int> > q;
    q.push({0, 0});

    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();

        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];
                    q.push({d, e}); // Push valid neighbor
                }
            }
        }
    }
//if(level[n-1][m-1]==0)
//{
//	level[n-1][m-1]=(f!=0)+(r!=0);
//}
//    // Output the shortest path weight to the bottom-right corner
    cout << level[n-1][m-1] +(f!=0)+(r!=0)<< endl;

    return 0;
}

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