PVOI14_2 - CHỌN ROBOT

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Thầy Minh mới đấu thầu một khu du lịch rộng lớn tại Hạ Long. Bản đồ vùng đất là một lưới ô vuông N*N được chia làm lưới ô vuông đơn vị, các hàng của lưới được đánh số từ 1 tới N từ trên xuống, và các cột của lưới được đánh số từ 1 tới N từ trái qua phải. Ô nằm trên giao của hàng i và cột j được gọi là ô (i, j) và có độ cao là A(i,j).

Thầy Minh muốn mua một robot để đi lại trên vùng đất này. Robot loại D thì có khả năng di chuyển giữa 2 ô kề cạnh nếu như chênh lệch độ cao giữa 2 ô đúng bằng D.

Hãy giúp thầy Minh chọn loại robot để có thể đặt xe vào một ô trên bảng sao cho từ ô đó đi được tới nhiều ô khác nhất.

Input

  • Dòng 1 chứa số nguyên dương N ≤ 1000
  • N dòng tiếp theo, dòng thứ i chứa N số nguyên không âm, số thứ j là A(i,j) ≤ 10 6 .

Các số trên một dòng của file input được ghi cách nhau bởi dấu cách.

Output

Ghi ra một số nguyên duy nhất là số ô mà robot có thể đi tới được theo phương án chọn robot và chọn ô xuất phát của bạn (tính cả ô xuất phát).

Example 

Input:
5
0 3 6 3 0 
3 7 0 7 3 
0 0 9 0 6 
3 7 0 7 9 
0 3 6 3 6

Output:
16

  • Người up: voj
  • Nguồn bài: PreVOI 2014