Untitled

 avatar
neyjrxdung
plain_text
2 months ago
3.3 kB
3
Indexable
Never
import java.util.Scanner;


class point_g{
	int x, y;
	point_g(int a, int b){
		x = a;
		y = b;
	}
}
class queue_g{
	int front = -1, end = -1;
	point_g[] data;
	queue_g(int size){
		data = new point_g[size];
	}
	void push(point_g p){
		data[++end] = p;
	}
	point_g pop(){
		return data[++front];
	}
	boolean isEmpty(){
		return front == end;
	}
	int size(){
		return end-front;
	}
	point_g get(int i){
		return data[i];
	}
}
public class Hugo_gold {
	static void solution(int[][] data, int[][] dataGold, int G, int x, int y, int[] resuilt, int[] flag, int[] countG, int[][] visitedGold){
		int[][] visited = new int[data.length][data[0].length];
		queue_g q = new queue_g(data.length*data[0].length);
		int[][] state = new int[data.length][data[0].length];
		int[][] visitedGoldT = new int[data.length][data[0].length]; 
		int[] row = {-1, 0, 1, 0};
		int[] col = {0, 1, 0, -1};
		visited[x][y] = 1;
		int count = 0;
		int state_temp = 0;
		q.push(new point_g(x, y));
		while(!q.isEmpty()){
			point_g p = q.pop();
			if(dataGold[p.x][p.y] == 2){
				visitedGoldT[p.x][p.y] = 1;
				flag[0] = 1;
				count++;
				if(state[p.x][p.y] > state_temp){
					state_temp = state[p.x][p.y];
				}
			}
			for(int i = 0; i < 4; i++){
				int xt = p.x + row[i];
				int yt = p.y + col[i];
				if(xt >= 0 && xt < data.length && yt >= 0 && yt < data[0].length && data[xt][yt] == 1 && visited[xt][yt] == 0){
					visited[xt][yt] = 1;
					state[xt][yt] = state[p.x][p.y] + 1;
					q.push(new point_g(xt, yt));
				}
			}
		}
		if(count >= countG[0]){
			if(count > countG[0]){
				countG[0] = count;
				resuilt[0] = state_temp;
				for(int i = 0; i < visitedGold.length; i++){
					for(int j = 0; j < visitedGold[0].length; j++){
						visitedGold[i][j] = visitedGoldT[i][j];
					}
				}
			}
			else{
				if(state_temp < resuilt[0]){
					resuilt[0] = state_temp;
					for(int i = 0; i < visitedGold.length; i++){
						for(int j = 0; j < visitedGold[0].length; j++){
							visitedGold[i][j] = visitedGoldT[i][j];
						}
					}
				}
			}
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int t = 1; t <= T; t++){
			int N = sc.nextInt();
			int G = sc.nextInt();
			int[][] dataGold = new int[N][N];
			int[][] visitedGold = new int[N][N];
			queue_g g = new queue_g(5);
			for(int i = 0; i < G; i++){
				int r = sc.nextInt()-1;
				int c = sc.nextInt()-1;
				dataGold[r][c] = 2;
				g.push(new point_g(r, c));
			}
			int[][] data = new int[N][N];
			for(int i = 0; i < N; i++){
				for(int j = 0; j < N; j++){
					data[i][j] = sc.nextInt();
				}
			}
			int[] resuilt = {999999};
			int[] flag = {0};
			int[] countG = {0};
			for(int i = 0; i < N; i++){
				for(int j = 0; j < N; j++){
					if(data[i][j] == 1 && dataGold[i][j] == 0){
						solution(data, dataGold, G, i, j, resuilt, flag, countG, visitedGold);
					}
				}
			}
			System.out.println("Case #"+t);
			if(flag[0] == 1){
				System.out.println(resuilt[0]);
				for(int i = 0; i < g.size(); i++){
					point_g p = g.get(i);
					if(visitedGold[p.x][p.y] == 0){
						System.out.println((p.x+1)+" "+(p.y+1));
					}
				}
			}
			else{
				System.out.println(-1);
			}
		}
	}

}
Leave a Comment