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

}

}


}

+ Recent posts