import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Solution {
static boolean Debug = false;
private static int T;
private static int MapSize;
private static int[][] Map;
private static int MaxSize;
private static int DesertMaxNo;
public static void main(String args[]) throws Exception {
BufferedReader br;
if (Debug) {
File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (10).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 = Integer.parseInt(br.readLine());
Map = new int[MapSize][];
DesertMaxNo = -1;
// Map 읽기
for (int i = 0; i < MapSize; i++) {
Map[i] = new int[MapSize];
st = new StringTokenizer(br.readLine());
for (int j = 0; j < MapSize; j++) {
Map[i][j] = Integer.parseInt(st.nextToken());
if(Map[i][j]>DesertMaxNo) {
DesertMaxNo = Map[i][j];
}
}
}
MaxSize = -1;
findPath();
System.out.println(String.format("#%d %d", T, MaxSize));
}
}
private static void findPath() {
int y, x;
for (int XY = 0; XY < MapSize * MapSize; XY++) {
// 모든 좌표 탐색
y = XY / MapSize;
x = XY % MapSize;
// 최대 이동범위 구하기 (왼쪽, 오른쪽)
int maxLeft = x;
int maxRight = (MapSize - 1) - x;
for (int i = maxLeft; i > 0; i--) {
for (int j = maxRight; j > 0; j--) {
// 수직크기 측정 (맵의 범위를 벗어나지 않도록)
if (i + j + y >= MapSize) {
continue;
}
// 해당 움직임의 디저트수
int eatSize = (i + j) * 2;
if (MaxSize < eatSize) {
// 더 작은 사이즈는 측정할 필요가 없음
if (eatDesert(XY, i, j) == true) {
MaxSize = eatSize;
}
}
}
}
}
}
// 탐색 순서를 고려하여 배치
static int[] rotY = { 1, 1, -1, -1 };
static int[] rotX = { 1, -1, -1, 1 };
private static boolean eatDesert(int XY, int left, int right) {
// XY: 현재좌표, left: 좌로 움직일 수 있는 범위, right: 우로 움직일수 있는 범위
int y = XY / MapSize;
int x = XY % MapSize;
int[] visited = new int[DesertMaxNo+1];
// ↘ 방향 right 번 -> ↙ 방향 left 번 -> ↖ 방향 right 번 -> ↗ 방향 left번
for (int i = 0; i < right; i++) {
y += rotY[0];
x += rotX[0];
if (visited[Map[y][x]]==1) {
return false;
} else {
visited[Map[y][x]] = 1;
}
}
for (int i = 0; i < left; i++) {
y += rotY[1];
x += rotX[1];
if (visited[Map[y][x]]==1) {
return false;
} else {
visited[Map[y][x]] = 1;
}
}
for (int i = 0; i < right; i++) {
y += rotY[2];
x += rotX[2];
if (visited[Map[y][x]]==1) {
return false;
} else {
visited[Map[y][x]] = 1;
}
}
for (int i = 0; i < left; i++) {
y += rotY[3];
x += rotX[3];
if (visited[Map[y][x]]==1) {
return false;
} else {
visited[Map[y][x]] = 1;
}
}
return true;
}
public static void log(String input) {
if (Debug) {
System.out.println(input);
}
}
public static void log(String input, Object... args) {
if (Debug) {
System.out.println(String.format(input, args));
}
}
}
'Knowledge > 알고리즘' 카테고리의 다른 글
백준: 14503번: 로봇 청소기 (0) | 2017.10.17 |
---|---|
1953. [모의 SW 역량테스트] 탈주범 검거 (0) | 2017.10.15 |
2383. [모의 SW 역량테스트] 점심 식사시간 (0) | 2017.10.15 |
2477. [모의 SW 역량테스트] 차량 정비소 (0) | 2017.10.10 |
1259. [S/W 문제해결 응용] 7일차 - 금속막대 (0) | 2017.10.08 |