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 Solution {
static boolean Debug = false;
static int MapSize, DigSize;
static int Highset;
static int[][] Map;
static int[][] Visited;
private static int T;
private static int Answer;
public static void main(String args[]) throws Exception {
BufferedReader br;
if (Debug) {
File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (4).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 , DigSize , 본문 예제
st = new StringTokenizer(br.readLine());
MapSize = Integer.parseInt(st.nextToken());
DigSize = Integer.parseInt(st.nextToken());
// 지도데이터
Map = new int[MapSize][];
Visited = new int[MapSize][];
Highset = 0;
for (int i = 0; i < MapSize; i++) {
Map[i] = new int[MapSize];
Visited[i] = new int[MapSize];
st = new StringTokenizer(br.readLine());
for (int j = 0; j < MapSize; j++) {
Map[i][j] = Integer.parseInt(st.nextToken());
if (Highset < Map[i][j]) {
Highset = Map[i][j];
}
}
}
// 길찾기 (시작점은 가장 큰 수)
ArrayList<Integer> startList = new ArrayList<>();
for (int i = 0; i < MapSize; i++) {
for (int j = 0; j < MapSize; j++) {
if (Highset == Map[i][j]) {
startList.add(i * MapSize + j);
}
}
}
Answer = 0;
for (int item : startList) {
findPath(item / MapSize, item % MapSize, 0);
}
System.out.println(String.format("#%d %d", T, Answer));
}
}
static int rotX[] = { 0, 1, 0, -1 };
static int rotY[] = { 1, 0, -1, 0 };
static Stack<Integer> pStack = new Stack<>();
// 모든 경로를 탐색하는 알고리즘
private static void findPath(int y, int x, int hint) {
Visited[y][x] = 1;
pStack.push(Map[y][x]);
Boolean isLast = true;
for (int i = 0; i < 4; i++) {
int moveY = y + rotY[i];
int moveX = x + rotX[i];
int path = isRight(moveY, moveX, Map[y][x]);
if (path == 1) { // 힌트 없이 전진
findPath(moveY, moveX, hint);
isLast = false;
} else if (path == 0 && hint == 0) {
// 힌트 사용하여 전진
findPath(moveY, moveX, 1);
isLast = false;
} else {
// 못간다.
}
}
if (isLast) {
// 모든 가능한 경로에 도달한 경우
int count = countLength(pStack);
if (count>0) {
if(Answer < count) {
Answer = count;
}
}
}
Visited[y][x] = 0;
pStack.pop();
}
// 탐색경로에서 길이를 체크해주는 함수
private static int countLength(Stack<Integer> inStack) {
ArrayList<Integer> list = new ArrayList<>();
list.addAll(inStack);
// [9, 7, 7, 3, 2]
// a = 7, b= 7, c =3
int temp = list.get(0);
int findIndex = -1;
int size = list.size();
for (int i = 1; i < size; i++) {
if (temp > list.get(i)) {
temp = list.get(i);
} else {
findIndex = i; // found b-index
break;
}
if(i==size-1) {
return list.size();
}
}
int a, b, c; // 오름차순
a = list.get(findIndex - 1);
b = list.get(findIndex);
c = (findIndex + 1 != list.size()) ? list.get(findIndex + 1) : -1;
if(((b - a) + 1 <= DigSize)) { // 땅을 팔 수 있는 경우
if(a > c + 1) { // c가 a보다 2이상 차이 나는 경우, 이 후 순서도 보장
return size;
}else { // c가 a보다 크거나 같은 경우
return findIndex + 1; // b까지 옳음 (b_index + 1개 )
}
}else {
return findIndex ; // b-1 까지 옳음 (b_index-1 + 1개 )
}
}
// 경로 가능성 판단
private static int isRight(int y, int x, int num) {
// 갈수 있으면 1, 숫자 크기 때문에 못가면 0, 범위 밖이면 -1, 방문했던 곳 -1
if (y < 0 || y >= MapSize || x < 0 || x >= MapSize) {
return -1;
}
if (Visited[y][x] == 1) {
return -1;
}
return Map[y][x] < num ? 1 : 0;
}
private static void log(String input) {
System.out.println(input);
}
}
'Knowledge > 알고리즘' 카테고리의 다른 글
2117. [모의 SW 역량테스트] 홈 방범 서비스 (0) | 2017.10.07 |
---|---|
2382. [모의 SW 역량테스트] 미생물 격리 (0) | 2017.10.07 |
2115. [모의 SW 역량테스트] 벌꿀채취 (0) | 2017.10.07 |
1952. [모의 SW 역량테스트] 수영장 (0) | 2017.10.07 |
[와우패스] 동서남북 복불복 (0) | 2017.10.05 |