Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
4.4 kB
2
Indexable
Never
package Pizza_Location;

import java.io.FileInputStream;
import java.util.Scanner;

public class pizza_location {
	static int k, r, m, n;
	static int [][] sol;
	static int [][] loc;
	static int sumPeople;
	static int [] res;
	static boolean [][] cntRes;
	static boolean [] visit;
	
	static void reset() {
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				cntRes[i][j] = false;
			}
		}
		for (int i = 0; i < m; i++) {
			res[i] = 0;
		}
		sumPeople = 0;
	}
	static void check(int a) {
		if (a > m) return;
		int sum = 0;
		for (int i = 0; i < m; i++) {
			sum += res[i];
		}
		
		if (sum == k) {
			int count = 0;
			for (int i = 0; i < n; i++) {
				visit[i] = false;
			}
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					if (res[i] == 1 && !visit[j] && cntRes[i][j]) {
						count += sol[2][j];
						visit[j] = true;
					}
				}
			}
			if (sumPeople < count) sumPeople = count;
			return;
		}
		for (int i = 1; i >= 0; i--) {
			res[a] = i;
			check(a+1);
		}
	}
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("F://eclipse//SRV//src//Pizza_Location//pizza.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			
			k = sc.nextInt();
			r = sc.nextInt();
			m = sc.nextInt();
			res = new int [m+1];
			loc = new int [2][m];
			for (int i = 0; i < m; i++) {
				loc[0][i] = sc.nextInt();
				loc[1][i] = sc.nextInt();
			}
			n = sc.nextInt();
			sol = new int [3][n];
			visit = new boolean [n];
			cntRes = new boolean [m][n];
			for (int i = 0; i < n; i++) {
				sol[0][i] = sc.nextInt();
				sol[1][i] = sc.nextInt();
				sol[2][i] = sc.nextInt();
			}
			
			reset();
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					if ((loc[0][i] - sol[0][j]) * (loc[0][i] - sol[0][j])
							+ (loc[1][i] - sol[1][j]) * (loc[1][i] - sol[1][j]) <= r * r) {
						cntRes[i][j] = true;
					}
				}
			}
			check(0);
			System.out.println(sumPeople);
		}
	}

}














package Battle_City;

import java.io.FileInputStream;
import java.util.Scanner;

public class battle_city {
	static int MAX_SIZE = 10000;
	static int front, rear;
	static int [][] queue = new int [2][MAX_SIZE];
	
	static void push(int x, int y) {
		if (rear == MAX_SIZE -1) rear = -1;
		rear++;
		queue[0][rear] = x;
		queue[1][rear] = y;
	}
	
	static void pop() {
		if (front == MAX_SIZE -1) front = -1;
		front++;
	}
	
	static boolean isEmpty() {
		return rear == front;
	}
	
	static int m, n;
	static int sx, sy, ex, ey;
	static char [][] map;
	static int [][] visit;
	static int [] dx = {0, 1, 0, -1};
	static int [] dy = {1, 0, -1, 0};
	
	static int move(int x1, int y1) {
		if (map[x1][y1] == 'E' || map[x1][y1] == 'T') return 1;
		else if (map[x1][y1] == 'B') return 2;
		return 100000;
	}
	
	static void bfs (int x, int y) {
		push(x, y);
		visit[x][y] = 0;
		while (!isEmpty()) {
			pop();
			int q = queue[0][front];
			int p = queue[1][front];
			for (int i = 0; i < 4; i++) {
				int x1 = q + dx[i];
				int y1 = p + dy[i];
				if (x1 >= 0 && x1 < m && y1 >= 0 && y1 < n) {
					int a = move(x1, y1);
					if (visit[x1][y1] > visit[q][p] + a) {
						visit[x1][y1] = visit[q][p] + a;
						push(x1, y1);
					}
				}
			}
		}
	}
	static void reset() {
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				visit[i][j] = 100000;
			}
		}
	}
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("F://eclipse//SRV//src//Battle_City//battle_city.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		for (int test_case = 1; test_case <= T; test_case++) {
			rear = front = -1;
			m = sc.nextInt();
			n = sc.nextInt();
			sc.nextLine();
			map = new char [m][n];
			visit = new int [m][n];
			reset();
			for (int i = 0; i < m; i++) {
				String a = sc.nextLine();
				for (int j = 0; j < n; j++) {
					map[i][j] = a.charAt(j);
					if (map[i][j] == 'Y') {
						sx = i;
						sy = j;
					} 
					if (map[i][j] == 'T') {
						ex = i;
						ey = j;
					}
				}
			}
			bfs(sx, sy);
			if (visit[ex][ey] == 100000) System.out.println(-1);
			else System.out.println(visit[ex][ey]);
		}
	}
}