main(){
for(k번){
SpringSummer();
FallWinter();
}
점수계산 후 출력
}
SpringSummer(){
dead_tree = 여름에 영양분이 될 나무 모음
// 봄
for(배열 전체를 탐색하면서){
if(해당 위치에 나무가 없으면) 패스
for(리스트에 들어있는 순서대로 나무를 꺼내서){
if(나무가 먹을 영양분이 땅에 남아있다면){
영양분을 먹고
나무가 자람
}else{ // 나무가 먹을 영양분이 없다면
여름에 영양분이 될 나무 리스트에 추가
}
}
}
for(dead_tree){
해당 나무의 위치에 age/2만큼의 양분을 더함
}
}
FallWinter(){
for(배열 전체를 탐색하면서){
// 겨울
(i,j)에 입력으로 주어진 만큼의 양분을 추가합니다.
// 가을
for(나무들을 검사하면서){
if(나무의 나이가 5의 배수면){
주변 8곳에 나무를 심습니다.
}
}
}
}
import java.util.*;
public class Main {
static int N,M,K;
static int[][] AddFood,Earth;
static LinkedList<Tree>[][] lst;
static int[] dx = {1,1,1,0,0,-1,-1,-1};
static int[] dy = {1,0,-1,1,-1,1,0,-1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
K = sc.nextInt();
AddFood = new int[N][N]; // 겨울에 기계가 추가하는 양분의 양
Earth = new int[N][N]; // 현재 토지의 양분
lst = new LinkedList[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
lst[i][j] = new LinkedList<Tree>();
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
AddFood[i][j] = sc.nextInt();
}
Arrays.fill(Earth[i], 5); // 현재 토지 초기화
}
// 입력으로 주어지는 나무
for (int m = 0; m < M; m++) {
int x = sc.nextInt();
int y = sc.nextInt();
int age = sc.nextInt();
lst[x-1][y-1].add(new Tree(x-1,y-1,age));
}
for (int k = 0; k < K; k++) {
SpringSummer();
FallWinter();
}
System.out.println(Score());
}
public static void SpringSummer() {
List<Tree> dead_tree = new ArrayList<Tree>(); // 여름에 양분이 될 나무 모음
// 봄
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int size = lst[i][j].size();
if(size == 0) continue;
// Collections.sort(lst[i][j], Collections.reverseOrder()); // age가 1인 나무를 addFirst한다면 내림차순 정렬을 할 필요가 없습니다.
for (int t = 0; t < size; t++) {
Tree val = lst[i][j].poll();
if(val.age<=Earth[i][j]) {
Earth[i][j] -= val.age;
val.age++;
lst[i][j].addLast(val);
}else{
// Earth[i][j]+=val.age/2; // 틀린 코드
// 처음에 곧바로 양분을 Earth에 추가했더니 오답이 출력되었습니다.
// 곧바로 양분을 더하면 다음 나무에 영향을 받기 때문입니다.
// 예제 테스트케이스의 마지막 문제가 85가 아닌 91이 나온다면 이러한 부분때문일 가능성이 큽니다.
dead_tree.add(val);
}
}
}
}
// 여름 - 영양분을 얻지 못한 나무를 모두 양분으로 만들어줍니다.
int size = dead_tree.size();
for (int i = 0; i < size; i++) {
Tree val = dead_tree.get(i);
Earth[val.x][val.y] += val.age/2;
}
}
public static void FallWinter() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// 겨울 - 가을에서 Earth가 활용되지 않기 때문에 먼저 갱신해도 상관 없습니다.
// 먼저 갱신하는 이유는 가을에서 size가 0인 경우는 continue해 모든 (i,j)가 실행되지 않기 때문입니다.
Earth[i][j] += AddFood[i][j];
// 가을 - 나이가 5의 배수인 나무가 증식합니다.
int size = lst[i][j].size();
if(size == 0) continue;
for (int k = 0; k < size; k++) {
Tree val = lst[i][j].get(k);
if(val.age%5 == 0) {
for (int d = 0; d < 8; d++) {
int nx = i+dx[d];
int ny = j+dy[d];
if(0<= nx && nx < N && 0<= ny && ny <N) {
lst[nx][ny].addFirst(new Tree(nx,ny,1)); // 새로생긴 나무를 lst의 앞에 추가시킴으로써 봄에 나이가 어린 나무가 우선적으로 양분을 섭취합니다.
}
}
}
}
}
}
}
// 최종 점수를 계산하는 메서드입니다.
// 모든 땅을 돌면서 나무의 개수(lst[i][j].size())를 다 더합니다.
public static int Score() {
int score = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
score += lst[i][j].size();
}
}
return score;
}
static class Tree implements Comparable<Tree>{
int x;
int y;
int age;
public Tree(int x, int y, int age) {
super();
this.x = x;
this.y = y;
this.age = age;
}
@Override
public String toString() {
return "Tree [x=" + x + ", y=" + y + ", age=" + age + "]";
}
@Override
public int compareTo(Tree o) {
// TODO Auto-generated method stub
return o.age - this.age;
}
}
}