TripTastic

#include <algorithm>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::max;
using std::min;
using std::vector;
 
int main() {
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int row_num;
		int col_num;
		int kid_num;
		std::cin >> row_num >> col_num >> kid_num;
 
		// arreglo de sumas de prefijos 2D de las habitaciones
		vector<vector<long long>> r_pref(row_num + 1, vector<long long>(col_num + 1));
		for (int r = 1; r <= row_num; r++) {
			for (int c = 1; c <= col_num; c++) {
				std::cin >> r_pref[r][c];
				r_pref[r][c] +=
				    r_pref[r - 1][c] + r_pref[r][c - 1] - r_pref[r - 1][c - 1];
			}
		}
 
		// Devuelve la suma de la capacidad de las habitaciones de (sr, sc) a (er, ec) inclusive
		auto rect_sum = [&](int sr, int er, int sc, int ec) {
			return r_pref[er + 1][ec + 1] - r_pref[sr][ec + 1] - r_pref[er + 1][sc] +
			       r_pref[sr][sc];
		};
 
		int best = -1;
		for (int r = 0; r < row_num; r++) {
			for (int c = 0; c < col_num; c++) {
				// Nos aseguramos de que la habitación misma pueda alojar al mentor
				if (rect_sum(r, r, c, c) == 0) { continue; }
 
				int lo = 0;
				int hi = max(row_num, col_num);
				int valid = -1;
				while (lo <= hi) {
					int mid = (lo + hi) / 2;
					int sr = max(0, r - mid), er = min(row_num - 1, r + mid);
					int sc = max(0, c - mid), ec = min(col_num - 1, c + mid);
					if (rect_sum(sr, er, sc, ec) - 1 >= kid_num) {
						valid = mid;
						hi = mid - 1;
					} else {
						lo = mid + 1;
					}
				}
 
				if (valid != -1) { best = best == -1 ? valid : min(best, valid); }
			}
		}
 
		cout << best << endl;
	}
}

import java.io.*;
import java.util.*;
 
public class TripTastic {
	/** @return la suma de la capacidad de las habitaciones de (sr, sc) a (er, ec) inclusive */
	static long rectSum(long[][] rPref, int sr, int er, int sc, int ec) {
		return rPref[er + 1][ec + 1] - rPref[sr][ec + 1] - rPref[er + 1][sc] +
		    rPref[sr][sc];
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
 
		StringTokenizer st = new StringTokenizer(br.readLine());
		int testNum = Integer.parseInt(st.nextToken());
		for (int t = 0; t < testNum; t++) {
			st = new StringTokenizer(br.readLine());
			int rowNum = Integer.parseInt(st.nextToken());
			int colNum = Integer.parseInt(st.nextToken());
			int kidNum = Integer.parseInt(st.nextToken());
 
			// arreglo de sumas de prefijos 2D de las habitaciones
			long[][] rPref = new long[rowNum + 1][colNum + 1];
			for (int r = 1; r <= rowNum; r++) {
				st = new StringTokenizer(br.readLine());
				for (int c = 1; c <= colNum; c++) {
					rPref[r][c] = Integer.parseInt(st.nextToken());
					rPref[r][c] +=
					    rPref[r - 1][c] + rPref[r][c - 1] - rPref[r - 1][c - 1];
				}
			}
 
			int best = -1;
			for (int r = 0; r < rowNum; r++) {
				for (int c = 0; c < colNum; c++) {
					// Nos aseguramos de que la habitación misma pueda alojar al mentor
					if (rectSum(rPref, r, r, c, c) == 0) { continue; }
 
					int lo = 0;
					int hi = Math.max(rowNum, colNum);
					int valid = -1;
					while (lo <= hi) {
						int mid = (lo + hi) / 2;
						int sr = Math.max(0, r - mid);
						int er = Math.min(rowNum - 1, r + mid);
						int sc = Math.max(0, c - mid);
						int ec = Math.min(colNum - 1, c + mid);
						if (rectSum(rPref, sr, er, sc, ec) - 1 >= kidNum) {
							valid = mid;
							hi = mid - 1;
						} else {
							lo = mid + 1;
						}
					}
 
					if (valid != -1) {
						best = (best == -1 ? valid : Math.min(best, valid));
					}
				}
			}
 
			out.println(best);
		}
 
		out.close();
		br.close();
	}
}

for _ in range(int(input())):
	row_num, col_num, kid_num = [int(i) for i in input().split()]
 
	# arreglo de sumas de prefijos 2D de las habitaciones
	r_pref = [[0 for _ in range(col_num + 1)] for _ in range(row_num + 1)]
	for r in range(1, row_num + 1):
		row = [int(i) for i in input().split()]
		for c in range(1, col_num + 1):
			r_pref[r][c] = row[c - 1]
			r_pref[r][c] += r_pref[r - 1][c] + r_pref[r][c - 1] - r_pref[r - 1][c - 1]
 
	def rect_sum(sr: int, er: int, sc: int, ec: int) -> int:
		""":return: la suma de la capacidad de las habitaciones de (sr, sc) a (er, ec) inclusive"""
		return (
			r_pref[er + 1][ec + 1]
			- r_pref[sr][ec + 1]
			- r_pref[er + 1][sc]
			+ r_pref[sr][sc]
		)
 
	best = -1
	for r in range(row_num):
		for c in range(col_num):
			# Nos aseguramos de que la habitación misma pueda alojar al mentor
			if rect_sum(r, r, c, c) == 0:
				continue
 
			lo = 0
			hi = max(row_num, col_num)
			valid = -1
			while lo <= hi:
				mid = (lo + hi) // 2
				sr = max(0, r - mid)
				er = min(row_num - 1, r + mid)
				sc = max(0, c - mid)
				ec = min(col_num - 1, c + mid)
				if rect_sum(sr, er, sc, ec) - 1 >= kid_num:
					valid = mid
					hi = mid - 1
				else:
					lo = mid + 1
 
			if valid != -1:
				best = valid if best == -1 else min(best, valid)
 
	print(best)