2014 Jan Silver Problem 2 Cross Country Skiing: Difference between revisions

Jump to navigation Jump to search

2014 Jan Silver Problem 2 Cross Country Skiing (edit)

Revision as of 05:50, 5 May 2023

6,334 bytes added ,  5 May 2023
→‎Code
No edit summary
Line 19: Line 19:
== Code ==
== Code ==


 
=== C++ ===
<pre>
<pre>
#include <bits/stdc++.h>
#include <bits/stdc++.h>
Line 101: Line 101:
</pre>
</pre>


=== C++ (BFS) ===
<pre>
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> elevation;
vector<vector<int>> destination;
int totalPoints, current;
int startX = -1, startY = -1;
int numRows, numCols;
int maxHeight = 0, minHeight = 1e9;
void bfs(int x, int y, int maxDiff) {
    queue<pair<int, int>> q;
    vector<vector<bool>> visited(numRows, vector<bool>(numCols, false));
    q.push({x, y});
    visited[x][y] = true;
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        current += destination[x][y];
        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];
            if (newX >= 0 && newX < numRows && newY >= 0 && newY < numCols &&
                !visited[newX][newY] && abs(elevation[newX][newY] - elevation[x][y]) <= maxDiff) {
                q.push({newX, newY});
                visited[newX][newY] = true;
            }
        }
    }
}
bool isReachable(int maxDiff) {
    current = 0;
    bfs(startX, startY, maxDiff);
    return current >= totalPoints;
}
int main() {
    freopen("ccski.in", "r", stdin);
    freopen("ccski.out", "w", stdout);
    cin >> numRows >> numCols;
    totalPoints = 0;
    elevation.resize(numRows, vector<int>(numCols, 0));
    destination.resize(numRows, vector<int>(numCols, 0));
    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j < numCols; j++) {
            cin >> elevation[i][j];
            maxHeight = max(maxHeight, elevation[i][j]);
            minHeight = min(minHeight, elevation[i][j]);
        }
    }
    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j < numCols; j++) {
            cin >> destination[i][j];
            totalPoints += destination[i][j];
            if (startX < 0 && destination[i][j] == 1) {
                startX = i;
                startY = j;
            }
        }
    }
    int high = maxHeight - minHeight + 1;
    int low = 0;
    while (low < high) {
        int mid = (low + high) / 2;
        if (isReachable(mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    cout << high << endl;
}
</pre>
=== Java ===
<pre>
import java.util.*;
import java.io.*;
public class Main {
    static int[][] elevation;
    static int[][] destination;
    static int totalPoints, current;
    static int startX = -1, startY = -1;
    static int numRows, numCols;
    static int maxHeight = 0, minHeight = 1000000000;
    static void bfs(int x, int y, int maxDiff, boolean[][] visited) {
        visited[x][y] = true;
        current += destination[x][y];
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];
            if (newX >= 0 && newX < numRows && newY >= 0 && newY < numCols &&
                !visited[newX][newY] && Math.abs(elevation[newX][newY] - elevation[x][y]) <= maxDiff) {
                bfs(newX, newY, maxDiff, visited);
            }
        }
    }
    static boolean isReachable(int maxDiff) {
        current = 0;
        boolean[][] visited = new boolean[numRows][numCols];
        bfs(startX, startY, maxDiff, visited);
        return current >= totalPoints;
    }
    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream("ccski.in"));
        System.setOut(new PrintStream(new FileOutputStream("ccski.out")));
        Scanner sc = new Scanner(System.in);
        numRows = sc.nextInt();
        numCols = sc.nextInt();
        totalPoints = 0;
        elevation = new int[numRows][numCols];
        destination = new int[numRows][numCols];
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                elevation[i][j] = sc.nextInt();
                maxHeight = Math.max(maxHeight, elevation[i][j]);
                minHeight = Math.min(minHeight, elevation[i][j]);
            }
        }
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                destination[i][j] = sc.nextInt();
                totalPoints += destination[i][j];
                if (startX < 0 && destination[i][j] == 1) {
                    startX = i;
                    startY = j;
                }
            }
        }
        int high = maxHeight - minHeight + 1;
        int low = 0;
        while (low < high) {
            int mid = (low + high) / 2;
            if (isReachable(mid)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        System.out.println(high);
        sc.close();
    }
}
</pre>
=== Python ===
<pre>
import sys
from typing import List
def bfs(x: int, y: int, max_diff: int, visited: List[List[bool]]) -> None:
    visited[x][y] = True
    global current
    current += destination[x][y]
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    for i in range(4):
        new_x = x + dx[i]
        new_y = y + dy[i]
        if (0 <= new_x < num_rows and 0 <= new_y < num_cols and
            not visited[new_x][new_y] and abs(elevation[new_x][new_y] - elevation[x][y]) <= max_diff):
            bfs(new_x, new_y, max_diff, visited)
def is_reachable(max_diff: int) -> bool:
    global current
    current = 0
    visited = [[False] * num_cols for _ in range(num_rows)]
    bfs(start_x, start_y, max_diff, visited)
    return current >= total_points
sys.stdin = open('ccski.in', 'r')
sys.stdout = open('ccski.out', 'w')
num_rows, num_cols = map(int, input().split())
total_points = 0
elevation = [list(map(int, input().split())) for _ in range(num_rows)]
destination = [list(map(int, input().split())) for _ in range(num_rows)]
max_height = max(max(row) for row in elevation)
min_height = min(min(row) for row in elevation)
start_x, start_y = -1, -1
for i in range(num_rows):
    for j in range(num_cols):
        if destination[i][j] == 1:
            start_x, start_y = i, j
            break
    if start_x != -1:
        break
high = max_height - min_height + 1
low = 0
while low < high:
    mid = (low + high) // 2
    if is_reachable(mid):
        high = mid
    else:
        low = mid + 1
print(high)
</pre>


[[Category:Yearly_2013_2014]]
[[Category:Yearly_2013_2014]]
[[Category:Silver]]
[[Category:Silver]]
Retrieved from "https://wiki.usaco.fun/index.php/Special:MobileDiff/462"

Navigation menu