import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;


class Dice {

private int[] face;


static final int Left = 1, Right = 2;

static final int Up = 3, Down = 4;


int top, bottom;

int north, south;

int west, east;


// 전개도를 펼쳤을 때, 가운데를 top이라 생각하고, 각각의 면에 index를 메김

public Dice() {

top = 1;

bottom = 6;

north = 2;

south = 5;

west = 4;

east = 3;


face = new int[7];

}


// 주사위 디버깅

private void printDice() {

Main.log("%2d%2d%2d", 0, north, 0);

Main.log("%2d%2d%2d", west, top, east);

Main.log("%2d%2d%2d", 0, south, 0);

Main.log("%2d%2d%2d", 0, bottom, 0);

}


// 주사위를 해당 방향에 굴린 후, 바닥면을 주사위로 옮긴다.

public int move(int direct, int num) {


// 주사위를 굴리면 전개도에서 4면의 변화가 생김

int temp;

switch (direct) {

case Up:

temp = north;

north = top;

top = south;

south = bottom;

bottom = temp;

break;

case Down:

temp = bottom;

bottom = south;

south = top;

top = north;

north = temp;

break;

case Left:

temp = west;

west = top;

top = east;

east = bottom;

bottom = temp;

break;

case Right:

temp = east;

east = top;

top = west;

west = bottom;

bottom = temp;

break;

}


// 윗면 출력

System.out.println(face[top]);

// printDice();


// 주사위 면 복사

int result;

result = face[bottom];

if (num != 0) {

face[bottom] = num;

}


return result;

}


}


public class Main {


private static boolean Debug = false;

private static int MapSize_Y;

private static int MapSize_X;

private static int[][] Map;

private static int[] Command;

private static Dice Dice;

private static int startY;

private static int startX;


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


BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st;


// 맵 크기

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

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

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


// 주사위 시작 위치

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

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

Command = new int[Integer.parseInt(st.nextToken())];


// 맵 읽기

Map = new int[MapSize_Y][];

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

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

Map[i] = new int[MapSize_X];

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

Map[i][j] = Integer.parseInt(st.nextToken());

}

}


// 커맨드 읽기

int clen = Command.length;

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

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

Command[i] = Integer.parseInt(st.nextToken());

}


Dice = new Dice();


MoveDice();

// System.out.println(MaxSafeCount);

}


// 1~4 동서북남

static int[] rotY = { 0, 0, 0, -1, 1 };

static int[] rotX = { 0, 1, -1, 0, 0 };


private static void MoveDice() {


int clen = Command.length;

int y = startY;

int x = startX;


int moveY, moveX;


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

int direct = Command[i];

moveY = y + rotY[direct];

moveX = x + rotX[direct];


if (!isRight(moveY, moveX)) {

continue;

}


// 바닥면의 경우

int mapValue = Map[moveY][moveX];

if (mapValue != 0) {

// 바닥에 0이 아닐때, 숫자는 주사위로 옮겨간다.

Dice.move(direct, mapValue);

Map[moveY][moveX] = 0;

} else {

// 바닥이 0이라면 , 숫자는 맵으로 옮겨간다.

int num = Dice.move(direct, mapValue);

Map[moveY][moveX] = num;

}


y = moveY;

x = moveX;

}

}


private static boolean isRight(int y, int x) {


if (x < 0 || y < 0 || x >= MapSize_X || y >= MapSize_Y) {

return false;

} else {

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 > 알고리즘' 카테고리의 다른 글

백준 12100번: 2048(Easy)  (0) 2017.10.19
백준 3190번: 뱀  (0) 2017.10.19
백준 14502번: 연구소  (0) 2017.10.17
백준 14501번: 퇴사  (0) 2017.10.17
백준 13458번: 시험 감독  (0) 2017.10.17

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.StringTokenizer;


class Virus {

int y, x;


public Virus(int y, int x) {

this.y = y;

this.x = x;

}

}


class Wall {

int y, x;


public Wall(int y, int x) {

this.y = y;

this.x = x;

}

}


public class Main {


private static boolean Debug = true;

private static int MapSize_Y;

private static int MapSize_X;

private static int[][] Map;

private static int[][] Visited;

private static ArrayList<Virus> vList;

private static ArrayList<Wall> wList;

private static int MaxSafeCount;

private static int OriginSafeCount;

private static int VirusCount;


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


BufferedReader br;

StringTokenizer st;


if (Debug && false) {

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (11).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}


// 맵 크기

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

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

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


vList = new ArrayList<>();

wList = new ArrayList<>();

OriginSafeCount = 0;

// 맵 읽기

int atom;

Map = new int[MapSize_Y][];

Visited = new int[MapSize_Y][];

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

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

Map[i] = new int[MapSize_X];

Visited[i] = new int[MapSize_X];

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

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

Map[i][j] = atom;

if (atom == 2) {

vList.add(new Virus(i, j));

OriginSafeCount++;

} else if(atom==0) {

wList.add(new Wall(i, j));

OriginSafeCount++;

}

}

}


MaxSafeCount = 0;

makeWall();

System.out.println(MaxSafeCount);

}


private static void makeWall() {

int wsize = wList.size();


Wall w1, w2, w3;

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

for (int j = i + 1; j < wsize; j++) {

for (int k = j + 1; k < wsize; k++) {

w1 = wList.get(i);

w2 = wList.get(j);

w3 = wList.get(k);

Map[w1.y][w1.x] = 1;

Map[w2.y][w2.x] = 1;

Map[w3.y][w3.x] = 1;


simulate();


Map[w1.y][w1.x] = 0;

Map[w2.y][w2.x] = 0;

Map[w3.y][w3.x] = 0;

}

}

}


}


private static void simulate() {


// 조건 초기화

Visited = new int[MapSize_Y][];

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

Visited[i] = new int[MapSize_X];

}

// log("s:%d, w:%d, v:%d", countMap(0), countMap(1), countMap(2));


VirusCount = 0;

int y, x;

for (Virus item : vList) {

y = item.y;

x = item.x;


if (Visited[y][x] == 0) {

findPath(y, x);

} else {

// Non-target

}

}


// log("s1:%d, w:%d, v:%d", countMap(0), countMap(1), countMap(2));

int safeCount = countMap(0);

if (MaxSafeCount < safeCount) {

MaxSafeCount = safeCount;

}


}


static int[] rotY = { 1, 0, -1, 0};

static int[] rotX = { 0, 1, 0, -1};


private static void findPath(int y, int x) {

Visited[y][x] = 1;

VirusCount++;

if(OriginSafeCount - VirusCount < MaxSafeCount) {

// break; 조건

return;

}

int moveY, moveX;

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


moveY = y + rotY[i];

moveX = x + rotX[i];


if (isRight(moveY, moveX)) {

findPath(moveY, moveX);

}

}


}


private static boolean isRight(int y, int x) {


if (y < 0 || y >= MapSize_Y || x < 0 || x >= MapSize_X) {

return false;

} else if (Visited[y][x] == 1 || Map[y][x] == 1) {

return false;

}


return true;

}


private static int countMap(int what) {


int count = 0;

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

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


if (what == 0) { // 빈공간의 수

if (Visited[i][j] == 0 && Map[i][j] == 0) {

count++;

}

} else if (what == 1) { // 벽의 수

if (Map[i][j] == 1) {

count++;

}

} else if (what == 2) { // 바이러스 영역의 수

if (Visited[i][j] == 1 || Map[i][j] == 2) {

count++;

}

}

}

}


return count;

}


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 > 알고리즘' 카테고리의 다른 글

백준 3190번: 뱀  (0) 2017.10.19
백준 14499번: 주사위 굴리기  (0) 2017.10.19
백준 14501번: 퇴사  (0) 2017.10.17
백준 13458번: 시험 감독  (0) 2017.10.17
백준: 14503번: 로봇 청소기  (0) 2017.10.17

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;


class Schedule {

int cost, pay;


public Schedule(int cost, int pay) {

this.cost = cost;

this.pay = pay;

}

}


public class Main {


private static boolean Debug = false;

private static int DateLen;

private static Schedule[] Date;

private static int MaxPayment;


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


BufferedReader br;

StringTokenizer st;


if (Debug && false) {

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (11).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}


// 일정의 길이

DateLen = Integer.parseInt(br.readLine());

Date = new Schedule[DateLen];


// 일정 읽기

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

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

Date[i] = new Schedule(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

}


MaxPayment = -1;

checkDate(0, 0);


System.out.println(MaxPayment);

}


private static void checkDate(int index, int sum) {


int cost = Date[index].cost;

int pay = Date[index].pay; 


int next = index + cost;


log("checkDate(%d) sum (%d) next(%d)", index, sum, next);


// 오늘 일정을 사용하고, 다음 일정으로 옮긴다.

if (next < DateLen) {

checkDate(next, sum + pay);

}


// 오늘 일정을 사용하지 않는 경우, 다음 일정으로 옮긴다. (단, 하루짜리 일정은 무조건 체킹)

if (cost != 1 && index + 1 < DateLen) {

checkDate(index + 1, sum);

}


int payment = (next <= DateLen ? sum + pay : sum);

log("최종금액: %d   sum: %d   next: %d", payment, sum, next);

if (MaxPayment < payment) {

MaxPayment = payment;

}


}



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

}

}


}




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80


import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;


public class Main {


private static boolean Debug = false;

private static int MapSize_Y;

private static int MapSize_X;

private static int[][] Map;

private static int[][] Visited;


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


BufferedReader br;

if (Debug && false) {

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (11).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}


StringTokenizer st;


// 맵의 크기를 받는다.

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

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

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


// 로봇의 위치를 받는다.

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

int startY = Integer.parseInt(st.nextToken());

int startX = Integer.parseInt(st.nextToken());

int rIndex = Integer.parseInt(st.nextToken());


// 맵 입력

Map = new int[MapSize_Y][];

Visited = new int[MapSize_Y][];

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

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

Map[i] = new int[MapSize_X];

Visited[i] = new int[MapSize_X];

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

Map[i][j] = Integer.parseInt(st.nextToken());

}

}


moveRobot(startY, startX, rIndex);


int count = 0;

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

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

if (Visited[i][j] == 1) {

count++;

}

}

}


System.out.println(count);

}


private static int[] rotY = { -1, 0, 1, 0 };

private static int[] rotX = { 0, 1, 0, -1 };


private static void moveRobot(int y, int x, int rIndex) {

Visited[y][x] = 1;

log("(%d,%d) 방문", y, x);


if (!isLeftClear(y, x, rIndex)) {

// Command 1

int nIndex = rIndex == 0 ? 3 : rIndex - 1;

int moveY = y + rotY[nIndex];

int moveX = x + rotX[nIndex];


moveRobot(moveY, moveX, nIndex);

} else if (!isAllClear(y, x)) {

// Command 2

int nIndex = rIndex == 0 ? 3 : rIndex - 1;

moveRobot(y, x, nIndex); // 방향 전환

} else if (isMoveBack(y, x, rIndex)) {

// Command 3

int nIndex = rIndex < 2 ? rIndex + 2 : rIndex - 2;

int moveY = y + rotY[nIndex];

int moveX = x + rotX[nIndex];

moveRobot(moveY, moveX, rIndex); // 방향은 유지한 채로 뒤로 한 발자국

} else {

// Command 4

log("I've Done");

}


}


// 로봇의 왼쪽 방향이 깨끗한지

private static boolean isLeftClear(int y, int x, int rIndex) {

int sIndex = rIndex == 0 ? 3 : rIndex - 1;

int moveY = y + rotY[sIndex];

int moveX = x + rotX[sIndex];


if (moveY < 0 || moveY >= MapSize_Y || moveX < 0 || moveX >= MapSize_X) {

return true;

} else if (Map[moveY][moveX] == 1) {

return true;

} else if (Visited[moveY][moveX] == 1) {

return true;

}


return false;

}


// 모든 방향 모두 깨끗한지

private static boolean isAllClear(int y, int x) {


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

if (!isLeftClear(y, x, i)) {

return false;

}

}


return true;

}


// 후진이 가능한지

private static boolean isMoveBack(int y, int x, int rIndex) {

int sIndex = rIndex < 2 ? rIndex - 2 + 4 : rIndex - 2;

int moveY = y + rotY[sIndex];

int moveX = x + rotX[sIndex];


if (moveY < 0 || moveY >= MapSize_Y || moveX < 0 || moveX >= MapSize_X) {

return false;

} else if (Map[moveY][moveX] == 1) {

return false;

}


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

}

}


}



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

private static int MapSize_X;

private static int FootSize;


private static int[][] Map; // 맵정보

private static int[][] Visited; // 시간정보

private static int[][] sTunnel; // 현재터널 방위측정

private static int[][] eTunnel; // 다음터널 방위측정


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


BufferedReader br;

if (Debug) {

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (11).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}


StringTokenizer st;


eTunnel = new int[8][];

eTunnel[1] = new int[] { 1, 1, 1, 1 };

eTunnel[2] = new int[] { 1, 0, 1, 0 };

eTunnel[3] = new int[] { 0, 1, 0, 1 };

eTunnel[4] = new int[] { 0, 0, 1, 1 };

eTunnel[5] = new int[] { 1, 0, 0, 1 };

eTunnel[6] = new int[] { 1, 1, 0, 0 };

eTunnel[7] = new int[] { 0, 1, 1, 0 };


sTunnel = new int[8][];

sTunnel[1] = new int[] { 1, 1, 1, 1 };

sTunnel[2] = new int[] { 1, 0, 1, 0 };

sTunnel[3] = new int[] { 0, 1, 0, 1 };

sTunnel[4] = new int[] { 1, 1, 0, 0 };

sTunnel[5] = new int[] { 0, 1, 1, 0 };

sTunnel[6] = new int[] { 0, 0, 1, 1 };

sTunnel[7] = new int[] { 1, 0, 0, 1 };


int TestSize = Integer.parseInt(br.readLine());

for (T = 1; T <= TestSize; T++) {


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

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

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


int doorY, doorX;

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

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


int time = Integer.parseInt(st.nextToken());


Visited = new int[MapSize_Y][];

Map = new int[MapSize_Y][];

// Map 읽기

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

Map[i] = new int[MapSize_X];

Visited[i] = new int[MapSize_X];

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

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

Map[i][j] = Integer.parseInt(st.nextToken());

Visited[i][j] = -1;

}

}


findPath(doorY, doorX, time - 1);

FootSize = 0;

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

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

if (Visited[i][j] != -1) {

FootSize++;

}

}

}


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


}


}


static int[] rotY = { -1, 0, 1, 0 };

static int[] rotX = { 0, 1, 0, -1 };


private static void findPath(int y, int x, int time) {

Visited[y][x] = time;


if (time == 0) {

// log(String.format("타임업 - 좌표(%d, %d) 시간: %d", y, x, time));

return;

}


// log(String.format("이동중 - 좌표(%d, %d) 시간: %d", y, x, time));

boolean isLast = true;

int nextY, nextX;

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

nextY = y + rotY[i];

nextX = x + rotX[i];


// 현재 터널에서 이동 가능한지 체크!

if (sTunnel[Map[y][x]][i] == 0) {

continue;

}


// 다음 경로에 진입할 수 있는지 체크!

if (isRight(nextY, nextX, i, time)) {

findPath(nextY, nextX, time - 1);

isLast = false;

}

}


}


public static boolean isRight(int y, int x, int rIndex, int time) {


if (x < 0 || x >= MapSize_X || y < 0 || y >= MapSize_Y) {

return false; // 배열 범위초과

} else if (Map[y][x] == 0) {

return false; // 벽

} else if (eTunnel[Map[y][x]][rIndex] == 0) {

return false; // 터널 이동 불가

} else if (Visited[y][x] > time) {

// 누군가가 방문했더라면, 나보다 먼저 방문했을 땐 못가고, 내가 더 먼저라면 갈 수 있다.

// 깊이 탐색이므로 시간 순으로 방문하지 않는다. 너비 탐색이라면 알아서 시간 순 탐색이니 신경쓰지 않아도 됨.

return false;

}


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

}

}


}

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

}

}


}

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

}

}


}

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.StringTokenizer;


class People {

int no;

int cept = -1;

int pair = -1;


public People(int no) {

this.no = no;

}


public void tag(int i) {


if (cept == -1) {

cept = i;

} else if (pair == -1) {

pair = i;

}

}



}


class Factory {


int seatSize;

int[] state;

People[] seat;


ArrayList<Integer> wList;

Queue<People> inQueue;

Queue<People> outQueue;


public Factory(ArrayList<Integer> wList, Queue inQueue, Queue outQueue) {

this.seatSize = wList.size();


this.wList = wList;

this.inQueue = inQueue;

this.outQueue = outQueue;


state = new int[seatSize];

seat = new People[seatSize];

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

state[i] = wList.get(i);

}

}


public void tick() {


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

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

state[i]--;

}

}


}


public void comeOut() {


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

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

outQueue.offer(seat[i]);

state[i] = wList.get(i);

seat[i] = null;

}

}


}


public void comeIn() {


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

if (state[i] == wList.get(i)) {

if (!inQueue.isEmpty()) {

seat[i] = inQueue.poll();

seat[i].tag(i+1);

// Solution.log(seat[i]!=null ?"O":"X");

}

}

}


}


}


class Solution {


static boolean Debug = true;

private static int T;


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


BufferedReader br;

if (Debug) {

// C:\Users\wvimi\Downloads\input (2).txt

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (8).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++) {


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

int ReceptSize = Integer.parseInt(st.nextToken());

int RepairSize = Integer.parseInt(st.nextToken());

int CustomerNum = Integer.parseInt(st.nextToken());

int ReceptUseNo = Integer.parseInt(st.nextToken());

int RepairUseNo = Integer.parseInt(st.nextToken());


// 좌석 마다 걸리는 시간

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

ArrayList<Integer> cepList = new ArrayList();

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

cepList.add(Integer.parseInt(st.nextToken()));

}

// 좌석 마다 걸리는 시간

ArrayList<Integer> piarList = new ArrayList();

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

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

piarList.add(Integer.parseInt(st.nextToken()));

}


// 고객 오는 스케줄

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

ArrayList<Integer> duleList = new ArrayList();

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

duleList.add(Integer.parseInt(st.nextToken()));

}


// 로비1(대기), 로비2(대기), 로비3(완료)

Queue<People> Robby1 = new LinkedList();

Queue<People> Robby2 = new LinkedList();

Queue<People> Robby3 = new LinkedList();


Factory cepFactory = new Factory(cepList, Robby1, Robby2);

Factory pairFactory = new Factory(piarList, Robby2, Robby3);


boolean isduleEnd = false;

int timer = -1;

while (true) {

timer++;


// Robby1에 손님 입장

if (!isduleEnd) {

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

// 시간이 되면 입장한다.

if (duleList.get(i) == timer) {

Robby1.offer(new People(i+1));

// 마지막 고객까지 나갔다면

if (i == CustomerNum) {

isduleEnd = true;

}

}

}

}


// 시간이 흐른다. (작업량 1감소)

cepFactory.tick();

pairFactory.tick();


// 완료된 사람은 다음 장소로 이동.

cepFactory.comeOut();

pairFactory.comeOut();


// 대기 중인 사람은 들어온다.

cepFactory.comeIn();

pairFactory.comeIn();


if (Robby3.size() == CustomerNum) {

// 모든 고객이 일을 마친다면...

break;

}

}


int Answer = 0;


People person;

while(!Robby3.isEmpty()) {

person = Robby3.poll();

// 지갑을 놓고온 접수, 수리 테이블을 이용한 고객을 추적

if(person.cept == ReceptUseNo && person.pair == RepairUseNo) {

Answer += person.no;

}else {

// Non-target

}

}


System.out.println(String.format("#%d %d", T, Answer > 0 ? Answer : -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));

}

}


}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
 
class Bar {
    int head, tail;
 
    public Bar(int head, int tail) {
        this.head = head;
        this.tail = tail;
    }
}
 
class Solution {
 
    static boolean Debug = false;
    static int BarSize;
 
    private static int T;
    private static int MaxCount;
    private static Queue<Integer> AnswerQueue;
 
    private static ArrayList<Bar> bList;
    private static int[] visited;
    private static int[] headInfo;
 
    public static void main(String args[]) throws Exception {
 
        BufferedReader br;
        if (Debug) {
            // C:\Users\wvimi\Downloads\input (2).txt
            File f = new File("디렉토리", "input (2).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++) {
 
            // BarSize ;
            st = new StringTokenizer(br.readLine());
            BarSize = Integer.parseInt(st.nextToken());
 
            // 초기화
            visited = new int[BarSize];
            headInfo = new int[BarSize];
            bList = new ArrayList<>();
 
            //
            Hashtable<Integer, Integer> startList = new Hashtable<>();
             
            // 시작의 경우의 수
            Bar item;
            int head, tail;
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < BarSize; i++) {
                head = Integer.parseInt(st.nextToken());
                tail = Integer.parseInt(st.nextToken());
                 
                item = new Bar(head, tail);
                bList.add(item);
                headInfo[i] = head;
                 
            }
 
            // 완전탐색
            MaxCount = 0;
            AnswerQueue = new LinkedList<>();
            for(int i=0; i <BarSize; i++) {
                findPath(i);
            }
             
            // log(MaxStack.toString());
             
            // 값 출력
            int index;
            Bar bar;
            String result = String.format("#%d", T);
            while(!AnswerQueue.isEmpty()) {
                index = AnswerQueue.poll();
                bar = bList.get(index);
                result += String.format(" %d %d", bar.head, bar.tail);
            }
 
            System.out.println(result);
        }
 
    }
 
    static Stack<Integer> bStack = new Stack();
    private static void findPath(int index) {
        visited[index] = 1;
        bStack.add(index);
 
        boolean isLast = true;
        int tail = bList.get(index).tail;
        for (int i = 0; i < BarSize; i++) {
            if (visited[i] == 0 && headInfo[i] == tail) {
                findPath(i);
                isLast = false;
            }
        }
         
        if(isLast) {
            // log("완성: " + bStack.toString());
            if(MaxCount < bStack.size()) {
                MaxCount = bStack.size();
                 
                AnswerQueue.clear();
                AnswerQueue.addAll(bStack);
            }
        }
 
        visited[index] = 0;
        bStack.pop();
    }
     
    private static void log(String input) {
        if (Debug) {
            System.out.println(input);
        }
    }
 
    private static void log(String input, Object... args) {
        if (Debug) {
            System.out.println(String.format(input, args));
        }
    }
 
}


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 Home {

int x, y;


public Home(int y, int x) {

this.y = y;

this.x = x;

}

}


class Solution {


static boolean Debug = false;

static int MapSize, ServFee;

static int[][] Map;

static ArrayList<Home> hList;


private static int T;

private static int MaxCount;


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


BufferedReader br;

if (Debug) {

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

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

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

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


// 맵 데이터 & 홈 집합

hList = new ArrayList<>();

Map = new int[MapSize][];

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] == 1) {

hList.add(new Home(i, j));

}

}

}


// 완전탐색

MaxCount = 0;

findPath();


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

}


}


private static void findPath() {


// [준비] 최대 방범 크기는?

int maxSize = -1;

for (int k = 1; ; k++) {

int profit = ServFee * hList.size() - (k * k + (k - 1) * (k - 1));

if (profit >= 0) {

maxSize = k;

} else {

break;

}

}

// log("hSize: %d  ,  maxSize: %d", hList.size(), maxSize);


int tempCount;

// 1. 크기를 적용한다.

for (int s = maxSize; s >= 0; s--) {

// 2. 좌표를 돈다.

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

// 해당 좌표에서 해당 크기에, 몇개의 집이 들어가는가?

tempCount = countHome(s, i);

// log("countHome(%d,%d) = %d", s, i, tempCount);

if (MaxCount < tempCount) {

MaxCount = tempCount;

}

}

}


}


private static int countHome(int scanSize, int xy) {

// log("countHome(%d,%d)", scanSize, xy);


int y = xy / MapSize;

int x = xy % MapSize;


Stack<Home> dStack = new Stack<>();

int gap;

for (Home home : hList) {

gap = ((x - home.x) > 0 ? (x - home.x) : (home.x - x));

gap += ((y - home.y) > 0 ? (y - home.y) : (home.y - y));


if (gap < scanSize) {

dStack.add(home);

} else {

// Non-target

}

}


int Profit = dStack.size() * ServFee;

Profit -= scanSize * scanSize + (scanSize - 1) * (scanSize - 1);


return Profit >= 0 ? dStack.size() : 0;

}


private static void log(String input) {

if (Debug) {

System.out.println(input);

}

}


private static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}


}

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 Virus {

int x, y;

int amount;

int rIndex;


public Virus(int y, int x, int amount, int rIndex) {

this.y = y;

this.x = x;

this.amount = amount;

this.rIndex = rIndex;

}


public int getXY() {

return Solution.MapSize * y + x;

}


}


class Solution {


static boolean Debug = false;

static int MapSize, TimeSize, VirusLen;

static ArrayList<Virus> vList;


private static int T;


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


BufferedReader br;

if (Debug) {

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

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

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

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

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


// 균데이터

vList = new ArrayList<>();

int y, x, amount, rIndex;

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

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

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

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

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

rIndex = Integer.parseInt(st.nextToken()) - 1;


vList.add(new Virus(y, x, amount, rIndex));

}


// 매초마다 시뮬레이션

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

moveVirus();

modifyVirus();

}


// 결과 출력

int sumAmount = 0;

for (Virus item : vList) {

sumAmount += item.amount;

}


// 길찾기 (시작점은 가장 큰 수)

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

}


}


private static void modifyVirus() {


int[] check = new int[MapSize * MapSize];

Stack<Integer> dStack = new Stack();


// 방향변경(반전) 및 해독제 효과(1/2)

for (Virus virus : vList) {


if (virus.x == 0 || virus.x == MapSize - 1) {

virus.rIndex = (virus.x == 0 ? 3 : 2); // 2(좌) 3(우)

virus.amount = virus.amount / 2;

} else if (virus.y == 0 || virus.y == MapSize - 1) {

virus.rIndex = (virus.y == 0 ? 1 : 0); // 0(상) 1(하)

virus.amount = virus.amount / 2;

}


// 중복값에 대한 좌표값 체크

// log("virus x:%d , y:%d", virus.x, virus.y);

if (++check[virus.getXY()] == 2) {

dStack.add(virus.getXY());

}


}


// 좌표가 중복되는  Virus

Stack<Virus> vStack = new Stack<>();

for (int xy : dStack) {

int maxAmount = -1;

int sumAmount = 0;


// 좌표가 같은 Virus 집단

for (Virus virus : vList) {

// log("v.amount: %d", virus.amount);


if (virus.getXY() == xy) {

vStack.add(virus);

sumAmount += virus.amount;

if (maxAmount < virus.amount) { // 같을 경우는 없다고 문제에서 가정

maxAmount = virus.amount;

}

} else {

// Non-target

}

}

// log("max: %d, sum: %d", maxAmount, sumAmount);

// 중복균 제거 & 병합

while (!vStack.isEmpty()) {

Virus virus = vStack.pop();

virus.amount = (virus.amount != maxAmount) ? 0 : sumAmount;

if (virus.amount == 0) {

vList.remove(virus);

}

}


}


}


// 상하좌우

static int[] rotX = { 0, 0, -1, 1 };

static int[] rotY = { -1, 1, 0, 0 };


private static void moveVirus() {

// 움직인다.

for (Virus virus : vList) {

int index = virus.rIndex;


virus.x = virus.x + rotX[index];

virus.y = virus.y + rotY[index];

}

}


private static void log(String input) {

if (Debug) {

System.out.println(input);

}

}


private static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}


}

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

}


}

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.Stack;

import java.util.StringTokenizer;


class Solution {


static boolean Debug = false;

static int MapSize, GetSize, Capacity;

static int[][] Map;

private static int MaxProfit;


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


BufferedReader br;

if (Debug) {

File f = new File("파일경로", "sample_input (3).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}


StringTokenizer st;


int T_Count = Integer.parseInt(br.readLine());

for (int T = 1; T <= T_Count; T++) {


// MapSize=4, GetSize=2, Capacity=13

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

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

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

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


// 지도데이터

Map = new int[MapSize][];

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

}

}


// 이용정보

MaxProfit = -1;

search();


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

}


}


private static void search() {


// 일꾼의 위치1, 위치2

int y1, x1, y2, x2;

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

for (int j = i; j < MapSize * MapSize; j++) {


y1 = i / MapSize;

x1 = i % MapSize;


y2 = j / MapSize;

x2 = j % MapSize;


if (isRight(y1, x1, y2, x2) == false) {

continue;

}


// 계산하기

calculate(y1, x1, y2, x2);


}

}


}


private static void calculate(int y1, int x1, int y2, int x2) {

// 현재 좌표에서 최대의 벌꿀 수익량

int maxOne = 0, maxTwo = 0;

int one, two;

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

// Case (벌꾼 담기)

one = getProfit(y1, x1, i);

two = getProfit(y2, x2, i);


if (maxOne < one) {

maxOne = one;

}


if (maxTwo < two) {

maxTwo = two;

}

}

if(MaxProfit < maxOne + maxTwo) {

MaxProfit = maxOne + maxTwo;

}

}


private static Stack<Integer> pStack = new Stack<>();


private static int getProfit(int y, int x, int bitmask) {


int amount = 0;

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

// 현재 경우에서 일꾼 1의 수익량

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

// i번째 꿀 수집

amount += Map[y][x + i];

pStack.push(Map[y][x + i]);

}

}


if (amount > Capacity) {

pStack.clear();

return 0;

} else {

int profit = 0;

int temp;

while (!pStack.isEmpty()) {

temp = pStack.pop();

profit += temp * temp;

}

return profit;

}

}


private static boolean isRight(int y1, int x1, int y2, int x2) {


if (y1 >= MapSize || y2 >= MapSize) {

// log("맵 사이즈 초과");

return false;

}

if (x1 + GetSize - 1 >= MapSize || x2 + GetSize - 1 >= MapSize) {

// log("맵 사이즈 초과");

return false;

}


int gap;

if (y1 == y2) {

gap = x1 - x2;

gap = gap > 0 ? gap : -gap;


if (gap < GetSize) {

return false;

}

}


return true;

}


private static void log(String input) {

if (Debug) {

System.out.println(input);

}

}


}

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.Arrays;

import java.util.Stack;

import java.util.StringTokenizer;


class Solution {


static boolean Debug = false;

static int[] Ticket = new int[4];

static int[] TicketCounter = new int[4];

static int[] Data = new int[12];

static int[] Visited = new int[12];

static int Data_Length = 12;

static int MIN_COST;

static int FIRST_DAY;


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


BufferedReader br;

if (Debug) {

File f = new File("파일경로", "sample_input.txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}


StringTokenizer st;


int T_Count = Integer.parseInt(br.readLine());

for (int T = 1; T <= T_Count; T++) {


// 가격정보

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

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

Ticket[i] = Integer.parseInt(st.nextToken());

TicketCounter[i] = 0;

}


FIRST_DAY = -1;

// 이용정보

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

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

Data[i] = Integer.parseInt(st.nextToken());

Visited[i] = (Data[i] == 0 ? 1 : 0);

if(FIRST_DAY == -1 && Data[i]!=0) {

FIRST_DAY = i;

}

}

MIN_COST = Integer.MAX_VALUE;

findFee();

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

}


}


static int[] rot = new int[] { 1, 30, 120, 360 };


static Stack<Integer> debug = new Stack();

private static void findFee() {


// 순차적 접근을 위하여, 가장 최초 index에서 시작

int next = -1;

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

if (Visited[i] == 0) {

next = i;

break; 

}

}

if (next == -1) {

log(debug.toString());

writeMinCost();

return;

}


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

if (!isRight(next, rot[i])) {

continue;

}

checkPay(next, i, true);

debug.add(i);

findFee();

checkPay(next, i, false);

debug.pop();

}


}


private static void checkPay(int index, int rindex, boolean isGo) {


if (rot[rindex] == 1) {

TicketCounter[rindex] += isGo ? Data[index] : -Data[index];

} else {

TicketCounter[rindex] += isGo ? 1 : -1;

}


switch (rot[rindex]) {

case 360:

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

if (Data[i] == 0) {

continue;

}

Visited[i] = isGo ? 1 : 0;

}

break;

case 120:

for (int i = index; (i < index + 3) && i < Data_Length; i++) {

if (Data[i] == 0) {

continue;

}

Visited[i] = isGo ? 1 : 0;

}

break;

case 30:

case 1:

if (Data[index] == 0) {

return;

}

Visited[index] = isGo ? 1 : 0;

break;

}


}


private static boolean isRight(int index, int day) {

if (Visited[index] == 1 || Data[index] == 0) {

return false;

}


// 비용계산

if (day == 360) {

return index == FIRST_DAY;

} else if (day == 120) {

return  Ticket[2] <= getCost(index, 1, 3) && Ticket[2] <= getCost(index, 30, 3);

} else if (day == 30) {

int month_fee = getCost(index, 30, 1);

int day_fee = getCost(index, 1, 1);

return month_fee <= day_fee;

} else if (day == 1) {

int month_fee = getCost(index, 30, 1);

int day_fee = getCost(index, 1, 1);

return month_fee >= day_fee;

}


return false;

}


private static int getCost(int index, int day, int length) {


if (day == 1) { // 1일로 구매한다면

int day_count = 0;

for (int i = index; i < index + length && i < Data_Length; i++) {

day_count += Data[i];

}

return day_count * Ticket[0];

} else if (day == 30) { // 1달로 구매한다면

int month_count = 0;

for (int i = index; i < index + length && i < Data_Length; i++) {

if (Data[i] > 0) {

month_count += 1;

}

}

return month_count * Ticket[1];

}


return Integer.MAX_VALUE;

}


private static void writeMinCost() {

int sum = 0;


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

if (TicketCounter[i] != 0) {

sum += (Ticket[i] * TicketCounter[i]);

}

}


if(MIN_COST>sum) {

MIN_COST = sum;

}

}


private static void log(String input) {

if (Debug) {

System.out.println(input);

}

}


}

+ Recent posts