Untitled
unknown
plain_text
12 days ago
6.1 kB
2
Indexable
Never
package Queue; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Moi_Dam_Cuoi { static int T, nodes, edges; static int nodeStart, nodeEnd; static int map[][], temp[][]; static int count, cNode, nNode; static boolean visited[]; public static class Queue{ static int front, rear, Data[]; public Queue() { this.front = this.rear = -1; Data = new int[1000000]; } public static void reset() { front = rear = -1; } public static void enQueue(int value) { Data[++rear] = value; } public static int deQueue() { return Data[++front]; } public static boolean is_Empty() { return front == rear; } } public static void countNode() { Queue queue = new Queue(); for(int i = 1; i <= nodes; i++) { if(i == nodeStart || i == nodeEnd) continue; else { for(int j = 1; j <= nodes; j++) { temp[i][j] = 0; temp[j][i] = 0; } queue.reset(); visited = new boolean[nodes+1]; queue.enQueue(nodeStart); visited[nodeStart] = true; boolean check = false; while(!queue.is_Empty()) { cNode = queue.deQueue(); for(int t = 1; t <= nodes; t++) { if(temp[cNode][t] == 1 && !visited[t]) { visited[t] = true; queue.enQueue(t); } if(temp[cNode][nodeEnd] == 1) { check = true; break; } } if(check) break; } if(!check) count++; for(int j = 1; j <= nodes; j++) { temp[i][j] = map[i][j]; temp[j][i] = map[j][i]; } } } } public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream("src/Queue/Moi_Dam_Cuoi")); Scanner scanner = new Scanner(System.in); T = scanner.nextInt(); for(int tc = 1; tc <= T; tc ++) { nodes = scanner.nextInt(); edges = scanner.nextInt(); nodeStart = scanner.nextInt(); nodeEnd = scanner.nextInt(); map = new int[nodes+1][nodes+1]; temp = new int[nodes+1][nodes+1]; int x, y ; for(int i = 1; i <= edges; i++) { x = scanner.nextInt(); y = scanner.nextInt(); map[x][y] = 1; temp[x][y] = 1; } count = 0; countNode(); System.out.println(count); } } } // Sky Force package Queue; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Sky_Force { static int T, N; static int map[][], bomb[][], countPoint[][]; static int cr, cc, nr, nc, maxPoint; static boolean check, visited[][]; static int dx[] = {-1, -1, -1}; static int dy[] = {-1, 0, 1}; public static class Queue{ static int front, rear, Data[]; public Queue() { this.front = this.rear = -1; Data = new int[1000000]; } public static void reset() { front = rear = -1; } public static void enQueue(int value) { Data[++rear] = value; } public static int deQueue() { return Data[++front]; } public static boolean is_Empty() { return front == rear; } } public static void calculatePoint() { int startR = N; int startC = 2; bomb = new int[N+1][N]; countPoint = new int[N+1][N]; visited = new boolean[N+1][N]; Queue rQueue = new Queue(); Queue cQueue = new Queue(); rQueue.enQueue(startR); cQueue.enQueue(startC); bomb[startR][startC] = 1; visited[startR][startC] = true; while(!rQueue.is_Empty()) { cr = rQueue.deQueue(); cc = cQueue.deQueue(); for(int i = 0; i < 3; i++) { nr = cr + dx[i]; nc = cc + dy[i]; if(nr < 0 || nc < 0 || nc >= 5) continue; if(bomb[cr][cc] == 1 && map[nr][nc] == 2) { if(!visited[nr][nc]) { countPoint[nr][nc] = countPoint[cr][cc]; bomb[nr][nc] = 0; rQueue.enQueue(nr); cQueue.enQueue(nc); visited[nr][nc] = true; } if(visited[nr][nc] && countPoint[nr][nc] <= countPoint[cr][cc]) { countPoint[nr][nc] = countPoint[cr][cc]; bomb[nr][nc] = 0; rQueue.enQueue(nr); cQueue.enQueue(nc); } } if(countPoint[cr][cc] > 0 && map[nr][nc] == 2) { if(!visited[nr][nc]) { countPoint[nr][nc] = countPoint[cr][cc] - 1; rQueue.enQueue(nr); cQueue.enQueue(nc); visited[nr][nc] = true; } if(visited[nr][nc] && countPoint[nr][nc] <= countPoint[cr][cc] - 1) { countPoint[nr][nc] = countPoint[cr][cc] - 1; rQueue.enQueue(nr); cQueue.enQueue(nc); bomb[nr][nc] = bomb[cr][cc]; } } if(map[nr][nc] == 1 || map[nr][nc] == 0) { if(!visited[nr][nc]) { countPoint[nr][nc] = countPoint[cr][cc] + map[nr][nc]; rQueue.enQueue(nr); cQueue.enQueue(nc); visited[nr][nc] = true; } if(visited[nr][nc] && countPoint[nr][nc] <= countPoint[cr][cc] + map[nr][nc]) { countPoint[nr][nc] = countPoint[cr][cc] + map[nr][nc]; rQueue.enQueue(nr); cQueue.enQueue(nc); bomb[nr][nc] = bomb[cr][cc]; } } } } } public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream("src/Queue/Sky_Force")); Scanner scanner = new Scanner(System.in); T = scanner.nextInt(); for(int tc = 1; tc <= T; tc++) { System.out.println("Case #" + tc); N = scanner.nextInt(); map = new int[N][5]; for(int i = 0; i < N; i++) { for(int j = 0; j < 5; j++) { map[i][j] = scanner.nextInt(); } } check = false; maxPoint = -1; calculatePoint(); for(int c = 0; c < 5 ; c++) { if(visited[0][c]) { check = true; if(maxPoint < countPoint[0][c]) maxPoint = countPoint[0][c]; } } for(int r = 0; r < N; r++) { for(int c = 0; c < 5; c++) { System.out.print(countPoint[r][c] + " "); } System.out.println(); } if(!check) System.out.println("-1"); else System.out.println(maxPoint); } } }
Leave a Comment