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

+ Recent posts