import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;
class Virus {
int x, y;
int amount;
int rIndex;
public Virus(int y, int x, int amount, int rIndex) {
this.y = y;
this.x = x;
this.amount = amount;
this.rIndex = rIndex;
}
public int getXY() {
return Solution.MapSize * y + x;
}
}
class Solution {
static boolean Debug = false;
static int MapSize, TimeSize, VirusLen;
static ArrayList<Virus> vList;
private static int T;
public static void main(String args[]) throws Exception {
BufferedReader br;
if (Debug) {
File f = new File("디렉토리", "sample_input (5).txt");
FileReader reader = new FileReader(f);
br = new BufferedReader(reader);
} else {
br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용
}
StringTokenizer st;
int TestSize = Integer.parseInt(br.readLine());
for (T = 1; T <= TestSize; T++) {
// MapSize , TimeSize , VirusLen;
st = new StringTokenizer(br.readLine());
MapSize = Integer.parseInt(st.nextToken());
TimeSize = Integer.parseInt(st.nextToken());
VirusLen = Integer.parseInt(st.nextToken());
// 균데이터
vList = new ArrayList<>();
int y, x, amount, rIndex;
for (int i = 0; i < VirusLen; i++) {
st = new StringTokenizer(br.readLine());
y = Integer.parseInt(st.nextToken());
x = Integer.parseInt(st.nextToken());
amount = Integer.parseInt(st.nextToken());
rIndex = Integer.parseInt(st.nextToken()) - 1;
vList.add(new Virus(y, x, amount, rIndex));
}
// 매초마다 시뮬레이션
for (int i = 0; i < TimeSize; i++) {
moveVirus();
modifyVirus();
}
// 결과 출력
int sumAmount = 0;
for (Virus item : vList) {
sumAmount += item.amount;
}
// 길찾기 (시작점은 가장 큰 수)
System.out.println(String.format("#%d %d", T, sumAmount));
}
}
private static void modifyVirus() {
int[] check = new int[MapSize * MapSize];
Stack<Integer> dStack = new Stack();
// 방향변경(반전) 및 해독제 효과(1/2)
for (Virus virus : vList) {
if (virus.x == 0 || virus.x == MapSize - 1) {
virus.rIndex = (virus.x == 0 ? 3 : 2); // 2(좌) 3(우)
virus.amount = virus.amount / 2;
} else if (virus.y == 0 || virus.y == MapSize - 1) {
virus.rIndex = (virus.y == 0 ? 1 : 0); // 0(상) 1(하)
virus.amount = virus.amount / 2;
}
// 중복값에 대한 좌표값 체크
// log("virus x:%d , y:%d", virus.x, virus.y);
if (++check[virus.getXY()] == 2) {
dStack.add(virus.getXY());
}
}
// 좌표가 중복되는 Virus
Stack<Virus> vStack = new Stack<>();
for (int xy : dStack) {
int maxAmount = -1;
int sumAmount = 0;
// 좌표가 같은 Virus 집단
for (Virus virus : vList) {
// log("v.amount: %d", virus.amount);
if (virus.getXY() == xy) {
vStack.add(virus);
sumAmount += virus.amount;
if (maxAmount < virus.amount) { // 같을 경우는 없다고 문제에서 가정
maxAmount = virus.amount;
}
} else {
// Non-target
}
}
// log("max: %d, sum: %d", maxAmount, sumAmount);
// 중복균 제거 & 병합
while (!vStack.isEmpty()) {
Virus virus = vStack.pop();
virus.amount = (virus.amount != maxAmount) ? 0 : sumAmount;
if (virus.amount == 0) {
vList.remove(virus);
}
}
}
}
// 상하좌우
static int[] rotX = { 0, 0, -1, 1 };
static int[] rotY = { -1, 1, 0, 0 };
private static void moveVirus() {
// 움직인다.
for (Virus virus : vList) {
int index = virus.rIndex;
virus.x = virus.x + rotX[index];
virus.y = virus.y + rotY[index];
}
}
private static void log(String input) {
if (Debug) {
System.out.println(input);
}
}
private static void log(String input, Object... args) {
if (Debug) {
System.out.println(String.format(input, args));
}
}
}
'Knowledge > 알고리즘' 카테고리의 다른 글
1259. [S/W 문제해결 응용] 7일차 - 금속막대 (0) | 2017.10.08 |
---|---|
2117. [모의 SW 역량테스트] 홈 방범 서비스 (0) | 2017.10.07 |
1949. [모의 SW 역량테스트] 등산로 조성 (0) | 2017.10.07 |
2115. [모의 SW 역량테스트] 벌꿀채취 (0) | 2017.10.07 |
1952. [모의 SW 역량테스트] 수영장 (0) | 2017.10.07 |