입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.
테스트 케이스의 첫 번째 줄에는 총 이동 시간(M), BC의 개수(A)가 주어진다.
그 다음 2개의 줄에는 각각 사용자 A와 B의 이동 정보가 주어진다.
한 사용자의 이동 정보는 M개의 숫자로 구성되며, 각각의 숫자는 다음과 같이 매초마다 이동 방향을 의미한다.
숫자 | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
이동 방향 | 이동하지 않음 | 상 (UP) | 우 (RIGHT) | 하 (DOWN) | 좌 (LEFT) |
그 다음 줄에는 A개의 줄에 걸쳐 BC의 정보가 주어진다.
하나의 BC 정보는 좌표(X, Y), 충전 범위(C), 처리량(P)로 구성된다.
출력은 "#t"를 찍고 한 칸 띄운 다음 정답을 출력한다. (t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)
정답은 모든 사용자의 충전량 합의 최대값을 출력한다.
5
20 3
2 2 3 2 2 2 2 3 3 4 4 3 2 2 3 3 3 2 2 3
4 4 1 4 4 1 4 4 1 1 1 4 1 4 3 3 3 3 3 3
4 4 1 100
7 10 3 40
6 3 2 70
…
#1 1200
#2 3290
#3 16620
#4 40650
#5 52710
이 문제는 문제에서 주어진 조건들을 정확히 구현하려고 코딩을 하면 문제없이 풀 수 있다. HashMap을 이용해서 BC의 정보를 저장하고 빠르게 검색할 수 있도록 구현했다.
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.HashMap;
import java.util.ArrayList;
class Solution
{
static int[] dx = {0, -1, 0, 1, 0};
static int[] dy = {0, 0, 1, 0, -1};
static HashMap<Integer, Ap> map;
public static void main(String args[]) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int test_case = 1; test_case <= T; test_case++)
{
String[] input = br.readLine().split(" ");
int M = Integer.parseInt(input[0]);
int N = Integer.parseInt(input[1]);
int[] a = new int[M];
int[] b = new int[M];
map = new HashMap<>();
int t = 0;
Pair A = new Pair(1, 1);
Pair B = new Pair(10, 10);
int ans = 0;
input = br.readLine().split(" ");
for(int i=0; i<M; i++)
a[i] = Integer.parseInt(input[i]);
input = br.readLine().split(" ");
for(int i=0; i<M; i++)
b[i] = Integer.parseInt(input[i]);
for(int i=0; i<N; i++) {
input = br.readLine().split(" ");
map.put(i, new Ap(Integer.parseInt(input[1]), Integer.parseInt(input[0]), Integer.parseInt(input[2]), Integer.parseInt(input[3])));
}
while(true) {
ArrayList<Integer> listA = new ArrayList<>();
ArrayList<Integer> listB = new ArrayList<>();
int max = Integer.MIN_VALUE;
for(int i=0; i<N; i++) {
Ap ap = map.get(i);
if(Math.abs(A.x-ap.x)+Math.abs(A.y-ap.y)<=ap.c)
listA.add(i);
if(Math.abs(B.x-ap.x)+Math.abs(B.y-ap.y)<=ap.c)
listB.add(i);
}
if(listA.size()==0 && listB.size()==0) {
max = 0;
}
else if(listA.size()==0 || listB.size()==0) {
if(listA.size()==0) {
for(int i=0; i<listB.size(); i++) {
int idx = listB.get(i);
Ap y = map.get(idx);
max = Math.max(max, y.p);
}
}
else {
for(int i=0; i<listA.size(); i++) {
int idx = listA.get(i);
Ap x = map.get(idx);
max = Math.max(max, x.p);
}
}
}
else {
for(int i=0; i<listA.size(); i++) {
int idx1 = listA.get(i);
Ap x = map.get(idx1);
for(int j=0; j<listB.size(); j++) {
int idx2 = listB.get(j);
Ap y = map.get(idx2);
int sum = 0;
if(idx1==idx2)
sum = x.p;
else
sum = x.p+y.p;
max = Math.max(max, sum);
}
}
}
ans += max;
if(t>=M) break;
int ax = A.x+dx[a[t]];
int ay = A.y+dy[a[t]];
int bx = B.x+dx[b[t]];
int by = B.y+dy[b[t]];
A = new Pair(ax, ay);
B = new Pair(bx, by);
t++;
}
System.out.println("#"+test_case+" "+ans);
}
}
public static class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public static class Ap {
int x;
int y;
int c;
int p;
public Ap(int x, int y, int c, int p) {
this.x = x;
this.y = y;
this.c = c;
this.p = p;
}
}
}