Fruit Matrix

0

0 votes
Medium
Problem

You are given a square matrix of size 'n x n'. Each element of the matrix denotes the number of fruits in that cell. You are also given a number 'k' (where 1 <= k <= n).

Consider a square sub-matrix of size 'k x k' inside the given matrix. You are allowed to touch only ONE cell inside this sub-matrix, and when you touch that cell, you get all the fruits of that cell.

Since, you love to eat fruits, you want to touch the cell with maximum number of fruits in the above 'k x k' sub-matrix. Let us call the maximum number of fruits as 'maxFruits' which you can get from this sub-matrix.

Your task is to print the 'maxFruits' for each of the sub-matrices of size 'k x k' inside the given matrix of size 'n x n'.

Input:-

First line contains 't', denoting the number of test cases. Then 't' lines follow, each containing the following:

'n k' (space-separated and without quotes), as explained in the question. Then, 'n' lines each containing 'n' space-separated integers, denoting the number of fruits in each cell (i.e. the input matrix).

Output:-

'n-k+1' lines containing 'n-k+1' space-separated integers denoting 'maxFruits' (explained in question) for all the sub-matrices of size 'k x k'.

Constraints:-

1 <= t <= 30
1 <= k <= n
0 <= (number of fruits in each cell) < 10^9
1 <= n <= 10^3

Problem Setter:-
Devesh Jagwani

Sample Input
2
4 2
1 2 3 4
7 9 15 6
8 13 2 1
20 5 8 9
6 3
10 20 30 8 90 5
47 1 289 49 13 4
284 2938 37 3 83 28
73 84 29 2 34 88
83 34 10 93 24 0
637 29 48 19 83 2
Sample Output
9 15 15 
13 15 15 
20 13 9 
2938 2938 289 90 
2938 2938 289 88 
2938 2938 93 93 
637 93 93 93
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

None

Editor Image

?