Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Question 2
- import java.io.*;
- import java.util.*;
- public class a {
- private static boolean[][] visited;
- private static ArrayList<HashSet<Integer>> bootsAccessible;
- private static class Boot {
- private int s;
- private int d;
- public Boot(int s, int d) {
- this.s = s;
- this.d = d;
- }
- }
- public static void main(String[] args) throws IOException {
- BufferedReader br = new BufferedReader(new FileReader("snowboots.in"));
- PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("snowboots.out")));
- StringTokenizer st = new StringTokenizer(br.readLine());
- int n = Integer.parseInt(st.nextToken());
- int b = Integer.parseInt(st.nextToken());
- int[] path = new int[n];
- st = new StringTokenizer(br.readLine());
- for(int i = 0; i < n; i++) {
- path[i] = Integer.parseInt(st.nextToken());
- }
- Boot[] boots = new Boot[b];
- for(int i = 0; i < b; i++) {
- st = new StringTokenizer(br.readLine());
- int s = Integer.parseInt(st.nextToken());
- int d = Integer.parseInt(st.nextToken());
- boots[i] = new Boot(s, d);
- }
- br.close();
- bootsAccessible = new ArrayList<HashSet<Integer>>();
- for(int i = 0; i < n; i++) {
- bootsAccessible.add(new HashSet<Integer>());
- for(int j = 0; j < b; j++) {
- if(boots[j].s >= path[i]) {
- bootsAccessible.get(i).add(j);
- }
- }
- }
- visited = new boolean[n][b];
- floodfill(0, 0, boots, n);
- int minBoots = 0;
- for(int i = 0; i < b; i++) {
- if(visited[n-1][i]) {
- minBoots = i;
- break;
- }
- }
- pw.print(minBoots);
- pw.close();
- }
- public static void floodfill(int tileInd, int bootInd, Boot[] boots, int n) {
- if(tileInd >= n || bootInd >= boots.length || visited[tileInd][bootInd]) {
- return;
- }
- visited[tileInd][bootInd] = true;
- for(int i = 1; i <= boots[bootInd].d; i++) {
- if(tileInd + i < n && bootsAccessible.get(tileInd + i).contains(bootInd)) {
- floodfill(tileInd + i, bootInd, boots, n);
- }
- }
- for(int i = bootInd + 1; i < boots.length; ++i) {
- if(bootsAccessible.get(tileInd).contains(i)) {
- floodfill(tileInd, i, boots, n);
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement