Submission #1092215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092215		brinton	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	844 ms	184908 KiB

tracks

// #include <bits/stdc++.h>
// using namespace std;
// int H,W;
// void dfs(int r,int c,vector<vector<int>>& matrix,vector<vector<int>>& minDist){
	// // cout << r << " " << c << endl;
	// int dx[4] = {0,1,-1,0};
	// int dy[4] = {1,0,0,-1};
	// for(int i = 0;i < 4;i++){
		// int newX = r+dx[i];
		// int newY = c+dy[i];
		// if(newX < 0 || newY < 0 || newX >= H || newY >= W){
			// continue;
		// }
		// if(matrix[newX][newY] == 0)continue;
		// int newDist = minDist[r][c];
		// if(matrix[newX][newY] != matrix[r][c]){
			// newDist++;
		// }
		// if(minDist[newX][newY] > newDist){
			// minDist[newX][newY] = newDist;
			// dfs(newX,newY,matrix,minDist);
		// }
	// }
// }
// int main(){
    // cin.tie(0);
    // ios_base::sync_with_stdio(0);
    // //start here
//     
    // cin >> H >> W;
    // vector<vector<int>> matrix(H,vector<int>(W,0));
//     
    // for(int i = 0;i < H;i++){
    	// for(int j = 0; j < W;j++){
    		// char tmp;
    		// cin >> tmp;
    		// if(tmp == 'F'){
    			// matrix[i][j] = 1;
    		// }else if(tmp == 'R'){
    			// matrix[i][j] = 2;
    		// }
    	// }
    // }
    // vector<vector<int>> min_dist(H,vector<int>(W,INT_MAX));
    // int ans = 0;
    // min_dist[0][0] = 1;
    // dfs(0,0,matrix,min_dist);
    // for(int i = 0; i < H;i++){
    	// for(int j = 0; j < W;j++){
    		// if(matrix[i][j] != 0){
    			// ans = max(min_dist[i][j],ans);
    			// // cout << min_dist[i][j] << " ";
    		// }
    		// // else{
    			// // cout << 0 << " ";
    		// // }
    	// }
    	// // cout << endl;
    // }
    // cout << ans;
// }
#include <bits/stdc++.h>
using namespace std;

int H, W;
int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};

int bfs_min_animals(vector<vector<int>>& matrix) {
    vector<vector<int>> min_dist(H, vector<int>(W, INT_MAX));
    deque<pair<int, int>> q;

    // Start from the top-left corner
    q.push_front({0, 0});
    min_dist[0][0] = 1;  // First animal starts at (0,0)

    while (!q.empty()) {
        int r = q.front().first;
        int c = q.front().second;
        q.pop_front();

        for (int i = 0; i < 4; ++i) {
            int newX = r + dx[i];
            int newY = c + dy[i];

            if (newX < 0 || newY < 0 || newX >= H || newY >= W) continue;
            if (matrix[newX][newY] == 0) continue; // Untouched snow

            // Calculate the new cost
            int newDist = min_dist[r][c];
            if (matrix[newX][newY] != matrix[r][c]) {
                newDist++;  // Different track, increase animal count
            }

            if (newDist < min_dist[newX][newY]) {
                min_dist[newX][newY] = newDist;
                if (matrix[newX][newY] == matrix[r][c]) {
                    q.push_front({newX, newY});  // Same track, prioritize by pushing to front
                } else {
                    q.push_back({newX, newY});  // Different track, explore later
                }
            }
        }
    }

    // The answer is the maximum value in the min_dist matrix
    int ans = 0;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (matrix[i][j] != 0) {
                ans = max(ans, min_dist[i][j]);
            }
        }
    }

    return ans;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> H >> W;
    vector<vector<int>> matrix(H, vector<int>(W, 0));

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            char tmp;
            cin >> tmp;
            if (tmp == 'F') {
                matrix[i][j] = 1;
            } else if (tmp == 'R') {
                matrix[i][j] = 2;
            }
        }
    }

    cout << bfs_min_animals(matrix) << "\n";

    return 0;
}

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