oj.uz

Submission #1092215

# Submission time Handle Problem Language Result Execution time Memory
1092215 2024-09-23T15:07:02 Z brinton Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 844 ms 184908 KB 
// #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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2648 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 9 ms 1880 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 3 ms 1116 KB Output is correct
15 Correct 10 ms 2652 KB Output is correct
16 Correct 12 ms 2680 KB Output is correct
17 Correct 10 ms 2396 KB Output is correct
18 Correct 6 ms 1884 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 54 ms 14172 KB Output is correct
3 Correct 322 ms 141392 KB Output is correct
4 Correct 94 ms 33612 KB Output is correct
5 Correct 164 ms 79680 KB Output is correct
6 Correct 814 ms 155952 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 2 ms 1084 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 1096 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 45 ms 14172 KB Output is correct
14 Correct 32 ms 8284 KB Output is correct
15 Correct 22 ms 9296 KB Output is correct
16 Correct 22 ms 5976 KB Output is correct
17 Correct 138 ms 36088 KB Output is correct
18 Correct 87 ms 35664 KB Output is correct
19 Correct 108 ms 33364 KB Output is correct
20 Correct 72 ms 30740 KB Output is correct
21 Correct 192 ms 82512 KB Output is correct
22 Correct 185 ms 79696 KB Output is correct
23 Correct 276 ms 68696 KB Output is correct
24 Correct 196 ms 80692 KB Output is correct
25 Correct 378 ms 141396 KB Output is correct
26 Correct 579 ms 158816 KB Output is correct
27 Correct 723 ms 184908 KB Output is correct
28 Correct 844 ms 156088 KB Output is correct
29 Correct 827 ms 153436 KB Output is correct
30 Correct 779 ms 158920 KB Output is correct
31 Correct 557 ms 91216 KB Output is correct
32 Correct 696 ms 164612 KB Output is correct