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

}

}


}

+ Recent posts