Untitled

mail@pastecode.io avatar
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