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));
}
}
}
'Knowledge > 알고리즘' 카테고리의 다른 글
2477. [모의 SW 역량테스트] 차량 정비소 (0) | 2017.10.10 |
---|---|
1259. [S/W 문제해결 응용] 7일차 - 금속막대 (0) | 2017.10.08 |
2382. [모의 SW 역량테스트] 미생물 격리 (0) | 2017.10.07 |
1949. [모의 SW 역량테스트] 등산로 조성 (0) | 2017.10.07 |
2115. [모의 SW 역량테스트] 벌꿀채취 (0) | 2017.10.07 |