N x N (N은 짝수) 크기의 무대 정중앙에 2 x 2 크기의 식물이 있다. 식물은 다음과 같이 춤을 춘다. 식물의 상하좌우와 맞닿은 면적 중 가장 큰 에너지 합을 가진 변으로 늘어난다. 춤을 출 때는 맞닿은 변의 에너지를 흡수하며 늘어난다. 더는 늘어날 수 없거나 섭취 가능한 에너지가 0 이하이면 춤을 멈춘다. 총 에너지 섭취량과 춤추는 방향 기록을 출력하면 된다. 방향은 상하좌우가 UDLR으로 나타낸다. 추가로 섭취 가능한 에너지가 동일할 때는 상하좌우 순으로 우선순위를 둔다.
매순간마다 상하좌우와 맞닿은 면의 에너지 총량을 구하고 가장 큰 에너지하을 가진 방향으로 이동한다. 만약 최대 에너지 총량이 0이거나 더는 이동할 수 없다면 종료한다.
// Input : Read size information
int N = Integer.parseInt(reader.readLine()); // Size of dancing stage
int[][] stage = new int[N][N]; // Energies of stage
// Input : Read energy information
StringTokenizer tokenizer;
for (int r = 0; r < N; r++) {
tokenizer = new StringTokenizer(reader.readLine());
for (int c = 0; c < N; c++) {
stage[r][c] = Integer.parseInt(tokenizer.nextToken());
}
}
// Dancing Plant
DancePlant dancePlant = new DancePlant(N, stage);
// Plant dances and save moving histories (UDLR)
StringBuilder history = new StringBuilder();
while (true) {
char direction = dancePlant.dance();
if (direction == ' ') break;
history.append(direction);
}
// Output : Print Energy eaten end history
result.append(dancePlant.getEnergy()).append('\n').append(history);
class DancePlant {
private int sr, sc, er, ec; // startRow, startCol, endRow, endCol
private final int[][] stage; // Energy information
private int energy; // Total energy eaten
private final char[] chars = {'U', 'D', 'L', 'R'};
public DancePlant(int size, int[][] stage) {
this.stage = stage;
sr = sc = size / 2 - 1;
er = ec = size / 2;
}
/**
* Dance one time
* @return Dancing direction
*/
public char dance() {
int maxEnergy = 0;
char direction = ' ';
for (int dir = 0; dir < 4; dir++) {
int sum = sideSum(dir);
if (sum > maxEnergy) {
maxEnergy = sum;
direction = chars[dir];
}
}
energy += maxEnergy;
switch (direction) {
case 'U' -> sr--;
case 'D' -> er++;
case 'L' -> sc--;
case 'R' -> ec++;
}
return direction;
}
/**
* Check side energy summation
* @param dir 0 U, 1 D, 2 L, 3 R
* @return Summation of energy
*/
private int sideSum(int dir) {
return switch (dir) {
case 0 -> sum(sc, ec, sr - 1, true);
case 1 -> sum(sc, ec, er + 1, true);
case 2 -> sum(sr, er, sc - 1, false);
case 3 -> sum(sr, er, ec + 1, false);
default -> throw new IllegalArgumentException("Should not reach here");
};
}
/**
* Calculate total energy of one side
* @param from Range from info
* @param to Range to info
* @param base Fixed info
* @param vertical Moving direction (true UD, false LR)
* @return Summation of one side energy
*/
private int sum(int from, int to, int base, boolean vertical) {
try {
int sum = 0;
for (int i = from; i <= to; i++)
sum += stage[vertical ? base : i][vertical ? i : base];
return sum;
} catch (ArrayIndexOutOfBoundsException e) {
return 0;
}
}
public int getEnergy() {
return energy;
}
}