import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Stack;

import java.util.StringTokenizer;


class Stair {

int y, x; // 계단의 위치

int cost; // 계단 내려가는데 걸리는 시간

int[] state; // 내려가는 정도

Person[] seat; // 계단 위에 있는 사람들

Queue<Person> inQueue; // 계단 입구

Queue<Person> outQueue; // 계단 출구


public Stair(int y, int x, int cost) {

this.y = y;

this.x = x;

this.cost = cost;


seat = new Person[3];

state = new int[3];

}


public void tick() {


// 작업량 감소 (계단 오르는 비용)

for (int i = 0; i < seat.length; i++) {


if (state[i] != 0 && seat[i] != null) {

state[i]--;

}


}


}


// 계단에서 나간다.

public void comeOut() {


for (int i = 0; i < seat.length; i++) {


if (state[i] == 0 && seat[i] != null) {

outQueue.offer(seat[i]);

seat[i] = null;

}


}


}


// 계단으로 들어온다.

public void comeIn() {


for (int i = 0; i < 3; i++) {

if (seat[i] == null) {

seat[i] = inQueue.poll();

state[i] = cost;

}

}


}


}


class Person {

int y, x;

int time;

int where;


public Person(int y, int x) {

this.y = y;

this.x = x;

}

}


class Solution {


static boolean Debug = false;

private static int T;

private static int MapSize;

private static ArrayList<Person> pList;

private static Stair[] Stair;

private static int PersonSize;

private static int MinTime;


public static void main(String args[]) throws Exception {


BufferedReader br;

if (Debug) {

File f = new File("디렉토리", "sample_input (9).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<>();

Stair = new Stair[2];


// [Input] 사람 객체를 생성하고 계단 객체를 생성한다.

for (int i = 0; i < MapSize; i++) {

st = new StringTokenizer(br.readLine());

int what;

for (int j = 0; j < MapSize; j++) {

what = Integer.parseInt(st.nextToken());

// 1. 사람이라면

if (what == 1) {

pList.add(new Person(i, j));

} else if (what > 1) { // 2.계단이라면

if (Stair[0] == null) {

Stair[0] = new Stair(i, j, what);

} else if (Stair[1] == null) {

Stair[1] = new Stair(i, j, what);

}

} else {

// Non-target

}

}

}


PersonSize = pList.size();

MinTime = Integer.MAX_VALUE;

// bitmask 값은 각 사람이 어떤 출구로 이동할까를 뜻한다.

for (int i = 0; i < (1 << PersonSize); i++) {

// 각 사람에게 위치와 시간을 지정

schedule(i);

// 시뮬레이션

simulate();

}


System.out.println(String.format("#%d %d", T, MinTime));

}


}


private static void simulate() {


// 0번 계단 입구, 1번 계단 입구, 출구

Queue<Person> Robby0, Robby1, Robby2;

Robby0 = new LinkedList<>();

Robby1 = new LinkedList<>();

Robby2 = new LinkedList<>();


// 계단의 입구와 출구 지정

Stair[0].inQueue = Robby0;

Stair[1].inQueue = Robby1;

Stair[0].outQueue = Robby2;

Stair[1].outQueue = Robby2;


ArrayList<Person> personList = new ArrayList<>();

personList.addAll(pList); // 출입 명단

Stack<Person> dStack = new Stack(); // 출입한 사람은 출입 명단에서 제거


int Timer = -1;

while (Robby2.size() != PersonSize) {

Timer++;


// 사람을 계단입구로 등장시킨다.

for (Person p : personList) {

if (p.time == Timer) {


if (p.where == 0) {

Robby0.offer(p);

} else if (p.where == 1) {

Robby1.offer(p);

}

dStack.add(p);

}

}


// 등장인물 리스트에서 제거

if (!dStack.isEmpty()) {

for (Person p : dStack) {

personList.remove(p);

}

dStack.clear();

}


Stair[0].tick(); // 작업량 감소

Stair[0].comeOut(); // 계단에서 나감

Stair[0].comeIn(); // 계단에 입장


Stair[1].tick();

Stair[1].comeOut();

Stair[1].comeIn();

}


if (MinTime > Timer) {

MinTime = Timer;

}


}


public static void schedule(int bitmask) {

// 상황(bitmask)에 따라서 Person 객체에 시간과 장소를 부여


int y0, x0, y1, x1;

y0 = Stair[0].y;

x0 = Stair[0].x;

y1 = Stair[1].y;

x1 = Stair[1].x;


Person person;

for (int i = 0; i < PersonSize; i++) {


person = pList.get(i);

if ((bitmask & (1 << i)) == 0) {

person.time = getTime(person, y0, x0);

person.where = 0;

// log("0번 출구로 %d만큼의 시간이 걸렸다.", person.time);

} else {

person.time = getTime(person, y1, x1);

person.where = 1;

// log("1번 출구로 %d만큼의 시간이 걸렸다.", person.time);

}


}


}


// xy 지점까지 가는 데 걸리는 시간

public static int getTime(Person p, int y, int x) {

// 계단 입구에 도착하고 1분 후에 내려간다. (1 + 이동시간)

return 1 + (p.x - x > 0 ? p.x - x : x - p.x) + (p.y - y > 0 ? p.y - y : y - p.y);

}


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));

}

}


}

+ Recent posts