Untitled
unknown
plain_text
5 months ago
7.1 kB
2
Indexable
Never
import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; class LocationInfo { boolean hasLake; boolean canExit; int numDiamond; public LocationInfo() { this.hasLake = false; this.canExit = false; this.numDiamond = 0; } public String toString() { String string = "0"; if (hasLake) string = "2"; if (canExit) string += ",3"; string = string + ", " + numDiamond; return string; } public int takeTimeToMove() { if (hasLake) return 2; return 1; } } class FireInfo { int X; int Y; int timeFireSpread; public FireInfo(int _x, int _y, int _t) { this.X = _x; this.Y = _y; this.timeFireSpread = _t; } public String toString() { return "(" + X + "," + Y + ", " + timeFireSpread + ")"; } } // FIFO class HQueue { private Node head; private Node tail; private int size = 0; public HQueue() { } public int size() { return size; } public boolean isEmpty() { if (head == null) return true; return false; } public void enqueue(FireInfo data) { size++; if (head == null) { head = new Node(data, head); tail = head; return; } if (data.timeFireSpread < head.data.timeFireSpread) { head = new Node(data, head); return; } Node run = head; while (run.next != null) { if (run.data.timeFireSpread <= data.timeFireSpread && data.timeFireSpread <= run.next.data.timeFireSpread) { break; } run = run.next; } if (run == tail) { tail.next = new Node(data); tail = tail.next; } else { Node newNode = new Node(data, run.next); run.next = newNode; } } public FireInfo dequeue() { if (head == null) throw new NullPointerException( "Queue is empty, so head value is null"); else { size--; Node temp = head; head = head.next; temp.next = null; return (FireInfo) temp.data; } } public FireInfo top() { if (head == null) throw new NullPointerException( "Stack is empty, so head value is null"); else { return (FireInfo) head.data; } } public void print() { System.out.print("{Queue}["); Node run = head; if (head == null) { System.out.println("]"); return; } while (run.next != null) { System.out.print(run.data + "<="); run = run.next; } System.out.println(run.data + "]"); } public void clear() { head = null; tail = head; } class Node { FireInfo data; Node next; public Node(FireInfo data) { this.data = data; this.next = null; } public Node(FireInfo data, Node next) { this.data = data; this.next = next; } } } public class Hugo { // 0: empty cell // 1: cell has fire // 2: cell has lake // 3: cell has exit private static LocationInfo[][] locationInfo; private static int[][] visited; private static int[][] timeFireSpread; private static int M, N, Xstart, Ystart; private static int maxAmountDiamond; private static int[] dx = { -1, 0, 1, 0 }; private static int[] dy = { 0, 1, 0, -1 }; private static void calculateTimeFire() { HQueue queue = new HQueue(); for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { if (timeFireSpread[i][j] == 0) { queue.enqueue(new FireInfo(i, j, 0)); } } } while (!queue.isEmpty()) { FireInfo currFireInfo = queue.dequeue(); for (int i = 0; i < 4; i++) { int Xc = currFireInfo.X + dx[i]; int Yc = currFireInfo.Y + dy[i]; if (Xc < 0 || Xc >= M) continue; if (Yc < 0 || Yc >= N) continue; if (timeFireSpread[Xc][Yc] == -1 && !locationInfo[Xc][Yc].hasLake) { timeFireSpread[Xc][Yc] = currFireInfo.timeFireSpread + 1; queue.enqueue(new FireInfo(Xc, Yc, timeFireSpread[Xc][Yc])); } } } // for (int i=0; i < M; i++) { // for (int j=0; j < N; j++) { // System.out.print(timeFireSpread[i][j] + "\t"); // } // System.out.println(); // } } public static void backtrack(int Xstart, int Ystart, int numDiamond, int timeTravel) { if (timeFireSpread[Xstart][Ystart] != -1 && timeTravel >= timeFireSpread[Xstart][Ystart]) { // System.out.println("DK 1"); return; } if (locationInfo[Xstart][Ystart].canExit) { // System.out.println("DK dung: " + numDiamond); if (maxAmountDiamond < numDiamond) maxAmountDiamond = numDiamond; } for (int i = 0; i < dx.length; i++) { int Xc = Xstart + dx[i]; int Yc = Ystart + dy[i]; if (Xc < 0 || Xc >= M) continue; if (Yc < 0 || Yc >= N) continue; // System.out.println("Move to: " + Xc + ", " + Yc); if (visited[Xc][Yc] == 0) { visited[Xc][Yc] = 1; // System.out.println("Time: " + (timeTravel + // locationInfo[Xc][Yc].takeTimeToMove())); backtrack(Xc, Yc, numDiamond + locationInfo[Xc][Yc].numDiamond, timeTravel + locationInfo[Xc][Yc].takeTimeToMove()); visited[Xc][Yc] = 0; } } } public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream("HugoFull")); Scanner sc = new Scanner(System.in); int num_tc = sc.nextInt(); for (int tc = 1; tc <= num_tc; tc++) { M = sc.nextInt(); N = sc.nextInt(); Xstart = sc.nextInt() - 1; Ystart = sc.nextInt() - 1; locationInfo = new LocationInfo[M][N]; visited = new int[M][N]; timeFireSpread = new int[M][N]; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { locationInfo[i][j] = new LocationInfo(); visited[i][j] = 0; timeFireSpread[i][j] = -1; } } // store length of arrays int n; // read fires position n = sc.nextInt(); for (int i = 0; i < n; i++) { int x = sc.nextInt() - 1; int y = sc.nextInt() - 1; timeFireSpread[x][y] = 0; } // read fires position n = sc.nextInt(); for (int i = 0; i < n; i++) { int x = sc.nextInt() - 1; int y = sc.nextInt() - 1; locationInfo[x][y].hasLake = true; } // read fires position n = sc.nextInt(); for (int i = 0; i < n; i++) { int x = sc.nextInt() - 1; int y = sc.nextInt() - 1; locationInfo[x][y].canExit = true; } for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { locationInfo[i][j].numDiamond = sc.nextInt(); } } // for (int i=0; i < M; i++) { // for (int j=0; j < N; j++) { // System.out.print(locationInfo[i][j] + "\t"); // } // System.out.println(); // } // maxAmountDiamond = Integer.MIN_VALUE; visited[Xstart][Ystart] = 1; calculateTimeFire(); // System.out.println("Hava: " + // locationInfo[Xstart][Ystart].numDiamond); backtrack(Xstart, Ystart, locationInfo[Xstart][Ystart].numDiamond, 0); maxAmountDiamond = maxAmountDiamond == Integer.MIN_VALUE ? -1 : maxAmountDiamond; System.out.println("Case #" + tc + "\n" + maxAmountDiamond); } } }