0.Hình vuông lớn nhất


Submit solution

Points: 3 (partial)
Time limit: 0.347s
Memory limit: 20M

Author:
Problem type

Cho ma trận có kích thước N x M. Các hàng của mỗi ma trận được đánh số từ 1 đến N từ trên xuống dưới. Các cột của mỗi ma trận được đánh số từ 1 đến M từ trái sang phải. Phần tử ở hàng i, cột j của ma trận A được ký hiệu là A[i][j].

Nhiệm vụ của bạn là tìm một hình vuông thỏa mãn các điều kiện:

  • Chỉ chứa các số 0 hoặc chỉ chứa các số 1.
  • Cạnh của hình vuông song song với cạnh của ma trận.
  • Cạnh của hình vuông là lớn nhất có thể.

Input:

Dòng 1: Ghi hai số N, M (1 <= N, M <= 1000)

N dòng tiếp theo, mỗi dòng chứa M số mà số thứ j là giá trị A[i][j].

Output:

Độ dài cạnh của hình vuông tìm được.

Example:

Input

10 10
1 1 1 0 1 1 1 1 1 1 
0 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 0 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 0 0  
0 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 0 1 1 1 1 1 
1 1 1 1 0 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1

Output

5

Comments


  • 0
    TICHPX  commented on Nov. 14, 2017, 7:52 p.m.

    Time limit:0.3457s