import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Stack;
import java.util.StringTokenizer;
class Point {
int y, x;
public Point(int y, int x) {
this.y = y;
this.x = x;
}
}
class Process {
int y, x;
public Process(int y, int x) {
this.y = y;
this.x = x;
}
HashSet<Point> moveSet = new HashSet();
public boolean on(int rIndex) {
// 해당 방향으로 전선을 잇는다.
int nextY = y;
int nextX = x;
int endIndex = Solution.MapSize - 1;
while (true) {
nextY += Solution.rotY[rIndex];
nextX += Solution.rotX[rIndex];
if (isRight(nextY, nextX)) {
// 경로기록
moveSet.add(new Point(nextY, nextX));
//경계지점에 도달
if (nextX == 0 || nextY == 0 || nextX == endIndex || nextY == endIndex) {
// 전선연결
for (Point item : moveSet) {
Solution.Visited[item.y][item.x] = 1;
}
return true;
}
} else {
// 경로 삭제
moveSet.clear();
return false;
}
}
}
public boolean isRight(int y, int x) {
if (x < 0 || y < 0 || x >= Solution.MapSize || y >= Solution.MapSize) {
// 배열범위
return false;
} else if (Solution.Visited[y][x] != 0) {
// 해당구획
return false;
}
return true;
}
public void off() {
// 전선을 제거한다.
for (Point item : moveSet) {
Solution.Visited[item.y][item.x] = 0;
}
moveSet.clear();
}
}
class Solution {
static boolean Debug = true;
private static int T;
static int MapSize;
static int[][] Visited; // 시간정보
private static ArrayList<Process> pList;
private static int processLen;
private static int[] checkMin;
public static void main(String args[]) throws Exception {
BufferedReader br;
if (Debug) {
File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (14).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());
// 프로세스 리스트
pList = new ArrayList<>();
Visited = new int[MapSize][];
// Map 읽기
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++) {
int item = Integer.parseInt(st.nextToken());
// 맵, Visited 초기화
Visited[i][j] = item == 1 ? 2 : item; // 0:빈공간, 1:방문, 2:프로세스
// 프로세스 등록
if (item == 1) {
boolean inner = i != 0 && j != 0 && i != MapSize - 1 && j != MapSize - 1;
if (inner) {
// 관리 프로세스에 등록
pList.add(new Process(i, j));
}
}
}
}
offProcLen = Integer.MAX_VALUE;
processLen = pList.size();
checkMin = new int[13];
// 최대 값을 저장할 배열
for (int i = 0; i < 13; i++) {
checkMin[i] = Integer.MAX_VALUE;
}
// 탐색
findPath(0, 0);
// 결과 출력
for (int i = 11; i >= 0; i--) {
// 성공한 길이를 탐색
if (checkMin[i] != Integer.MAX_VALUE) {
System.out.println(String.format("#%d %d", T, checkMin[i]));
break;
}
// 그 어떤 전선도 없는 경우
if (i == 0) {
System.out.println(String.format("#%d %d", T, 0));
}
}
}
}
static int offProcLen; // 도달한 0의 개수 (브레이크 조건으로 활용)
static Stack<Integer> debStack = new Stack();
private static void findPath(int index, int bitmask) {
// 끝지점에 도달
if (index == processLen) {
// 0을 몇 번 썼는지 체크
int count_one = countOne(bitmask);
int offLen = processLen - count_one;
if (offProcLen > offLen) {
offProcLen = offLen;
}
// 전선의 길이
int length = 0;
for (Process process : pList) {
length += process.moveSet.size();
}
// 프로세스 개수 별로 최대 개수를 달리한다.
if (checkMin[count_one] > length) {
checkMin[count_one] = length;
}
return;
}
Process item = pList.get(index);
// 프로세스에 전선을 잇는 경우
for (int i = 0; i < 4; i++) {
// 연결이 가능한 경우에만 탐색
int nextBitmask = bitmask + (1 << index);
// 최대 끌 수 있는 프로세스를 고려 (1개까지 꺼서 성공했으면, 2개는 허용 못함)
if (index + 1 - countOne(nextBitmask) <= offProcLen)
if (item.on(i)) {
// debStack.add(i + 1);
findPath(index + 1, nextBitmask);
item.off();
// debStack.pop();
}
}
// 프로세스에 전선을 잇지 않는 경우
// debStack.add(0);
findPath(index + 1, bitmask);
// debStack.pop();
}
static void printMap() {
for (int i = 0; i < MapSize; i++) {
String temp = "";
for (int j = 0; j < MapSize; j++) {
temp += Visited[i][j];
}
log(temp);
}
}
private static int countOne(int bitmask) {
int count = 0;
for (int i = 0; i < processLen; i++) {
if ((bitmask & (1 << i)) != 0) {
count++;
} else {
}
}
return count;
}
static int[] rotY = { -1, 0, 1, 0 };
static int[] rotX = { 0, 1, 0, -1 };
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 > 알고리즘' 카테고리의 다른 글
[스크랩] MD5 (위키백과) (0) | 2018.06.04 |
---|---|
백준 3671번: 산업 스파이의 편지 (0) | 2017.10.20 |
백준 14500번: 테트로미노 (0) | 2017.10.20 |
백준 13460번: 째로탈출2 (0) | 2017.10.20 |
백준 12100번: 2048(Easy) (0) | 2017.10.19 |