Problem1459--矩阵问题(超级弱化版)

1459: 矩阵问题(超级弱化版)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 128  Solved: 61
[Submit] [Status] [Web Board] [Creator:]

Description

给定一个n*n的矩阵,你可以从矩阵中任选一块正方形,但必须保证该正方形中所有数字之和小于等于m。
请问以(i,j)为左上角且符合以上要求的正方形中,边长最大的是多少?

Input

第一行两个正整数n,m,其中n<=30,m<=10^9。
接下来n行,每行n个非负整数aij,aij<=10^9。

Output

输出n行,每行n个数字。其中第i行第j个数字表示,以(i,j)为左上角且符合题目要求的正方形的最大边长。若以(i,j)为左上角没有符合要求的正方形,则输出0。

Sample Input

3 4
1 1 1
1 1 1
1 1 1

Sample Output

2 2 1
2 2 1
1 1 1

Source/Category