usaco why did the cow cross the road iii silver java

Solutions on MaxInterview for usaco why did the cow cross the road iii silver java by the best coders in the world

showing results for - "usaco why did the cow cross the road iii silver java"
Sophie
16 Oct 2019
1//sample input
23 3 3
32 2 2 3
43 3 3 2
53 3 2 3
63 3
72 2
82 3
9//CODE (2021/1/18) YY/MM/DD
10  import java.util.*;
11import java.io.*;
12public class Main {
13    static  field[][] farm;
14  public static void main(String[] args) throws Exception {
15    Scanner sc = new Scanner (new File("countcross.in"));
16    int n = sc.nextInt();//n x n grid
17    int k = sc.nextInt();// k cows
18    int r = sc.nextInt();// r roads
19     farm = new field[n][n];
20    for (int i = 0; i < n; i++) Arrays.fill(farm[i], new field());
21    for (int i = 0; i < r; i++) setRoad(new position(sc.nextInt(), sc.nextInt()), 
22                                        new position(sc.nextInt(), sc.nextInt()));
23    //floodFill
24    int no1 = 0;
25    for (int x = 0; x < n; x++ ){
26        for (int y = 0; y < n; y++){
27            if (!farm[x][y].visited){
28                floodFill(x, y, farm[x][y], no1);
29                no1++;
30            }
31        }
32    }
33    no1--;
34    int[] cows = new int[no1];
35    
36    for (int i = 0; i < k; i++){
37        int x = sc.nextInt();
38        int y = sc.nextInt();
39        int index = farm[x-1][y-1].fieldNum;
40        cows[index - 1]++;
41    }
42    int answer = 0; 
43    for (int i = 1; i < cows.length; i++){// when i = 0, it is in the default group, which means that it requires no road.
44        answer += k - cows[i];
45    }
46    PrintWriter out = new PrintWriter(new File("countcross.out"));
47    out.println(answer);
48    out.close();
49    sc.close();
50  }
51  static void floodFill(int x, int y, field thisF, int no1){
52      if (x < 0 || y < 0 || x >= farm.length || y >= farm[0].length) return; // Out of bound
53      if (thisF.visited) return; //visited
54      thisF = farm[x][y];
55      thisF.visited = true;
56      thisF.fieldNum = no1;
57      if (!thisF.fence[field.north]) floodFill(x, y+1, farm[x][y], no1);
58      if (!thisF.fence[field.south]) floodFill(x, y-1, farm[x][y], no1);
59      if (!thisF.fence[field.east]) floodFill(x+1, y, farm[x][y], no1);
60      if (!thisF.fence[field.west]) floodFill(x-1, y, farm[x][y], no1);
61  }
62  static void setRoad(position from, position to){
63      int dirF = from.pointTo(to);
64      int dirT = to.pointTo(from);
65      farm[from.x - 1][from.y - 1].fence[dirF] = true;
66      farm[to.x - 1][to.y - 1].fence[dirT] = true;
67  }
68}
69class field {
70    public boolean visited = false;
71    public int fieldNum = -1;
72    public boolean[] fence = new boolean[4];//NSWE
73    public field(){
74
75    }
76   static final int north = 0;
77   static final int south = 1;
78   static final int west = 2;
79   static final int east = 3;
80}
81class position {
82    public int x;
83    public int y;
84    public position(int x, int y){
85        this.x = x;
86        this.y = y;
87    }
88    public int pointTo(position a){
89        if (a.x > this.x) return field.east; if (a.x < this.x) return field.west;//x
90        if (a.y > this.y) return field.north; if (a.y < this.y) return field.south;//y
91        System.out.println("ERROR: poinTo");
92        return -1;
93    
94    }
95}
96//Output:
97     2