Cho một ma trận kích thước NxM. Với mỗi ô (i, j), một ô được gọi là "hàng xóm" nếu nó có chung cạnh với ô (i, j) (tức là ở phía trên, dưới, trái, phải). Hãy đếm xem trong ma trận có bao nhiêu ô mà giá trị của nó nghiêm ngặt lớn hơn tất cả các hàng xóm của nó (gọi là điểm cực đại địa phương).

Đầu vào:

Dòng 1: Hai số nguyên N, M.

N dòng tiếp theo: Mỗi dòng chứa M số nguyên dương A[i][j].

Đầu ra:

Một số nguyên duy nhất là số lượng ô thỏa mãn điều kiện.

Ràng buộc:

1 <= N, M <= 1000

1 <= A[i][j] <= 10^9

Ví dụ 1:

Input:

3 3 
1 2 1 
4 5 4 
1 2 1

Output:

1 

(Giải thích: Chỉ có số 5 ở giữa lớn hơn 2, 4, 4, 2)

Ví dụ 2:

Input:

3 3 
10 2 3 
4 5 6 
7 8 9

Output:

2 

(Giải thích: Số 10 và số 9 là các cực đại địa phương)

Cho ma trận NxM. Một "vùng ảnh hưởng" của ô (r, c) bao gồm chính nó và 8 ô xung quanh (trên, dưới, trái, phải, và 4 ô chéo). Hãy tính tổng giá trị của vùng ảnh hưởng lớn nhất trong ma trận.

Đầu vào:

Dòng 1: Hai số nguyên N, M.

N dòng tiếp theo: Mỗi dòng chứa M số nguyên A[i][j].

Đầu ra:

Tổng lớn nhất tìm được.

Ràng buộc:

3 <= N, M <= 1000

-10^5 <= A[i][j] <= 10^5

Ví dụ 1:

Input:

3 3 
1 1 1 
1 1 1 
1 1 1

Output:

9

Ví dụ 2:

Input:

4 4 
1 2 3 4 
5 6 7 8 
1 0 0 1 
1 1 1 1

Output:

31

(Giải thích: Tâm là số 7 hoặc 6 ở hàng 2 sẽ cho tổng lớn nhất khu vực 3x3 đó)

Cho một ma trận NxM chứa các số nguyên dương. Hai ô được gọi là liên thông nếu chúng có chung cạnh và cả hai đều chứa số nguyên tố. Một "vùng nguyên tố" là tập hợp các ô liên thông với nhau. Hãy tìm số lượng ô của "vùng nguyên tố" lớn nhất. (Lưu ý: Bài toán yêu cầu kiểm tra tính nguyên tố nhanh, cần sử dụng Sàng Eratosthenes).

Đầu vào:

Dòng 1: Hai số nguyên N, M.

N dòng tiếp theo: Ma trận A.

Đầu ra:

Diện tích (số lượng ô) của vùng nguyên tố lớn nhất.

Ràng buộc:

1 <= N, M <= 1000

1 <= A[i][j] <= 10^6 (Bắt buộc dùng sàng nguyên tố để không bị quá thời gian)

Ví dụ 1:

Input:

3 4 
2 3 5 4 
7 11 10 8 
13 4 2 2

Output:

6 

(Giải thích: Vùng 2-3-5-7-11-13 liên kết nhau)

Ví dụ 2:

Input:

3 3 
4 6 8 
9 10 12 
14 15 16

Output:

0

Sau trận mưa, trên sân kích thước NxM xuất hiện các vũng nước đọng. Số 1 biểu thị ô có nước, số 0 biểu thị ô đất khô. Hai ô nước được coi là cùng một "ao" nếu chúng liền kề nhau theo 4 hướng (trên, dưới, trái, phải). Hãy đếm số lượng ao nước trên sân.

Đầu vào:

Dòng 1: N, M.

N dòng tiếp theo: Các số 0 hoặc 1.

Đầu ra:

Số lượng ao.

Ràng buộc:

1 <= N, M <= 1000

Ví dụ 1:

Input:

3 4 
1 0 1 1 
1 0 0 1 
0 1 0 0

Output:

3

Ví dụ 2:

Input:

2 2 
1 1 
1 1

Output:

1

Cho ma trận NxM. Hãy tìm ô (i, j) sao cho tổng giá trị của nó và 4 ô xung quanh là một số có nhiều ước số nhất. In ra số lượng ước số đó.

Đầu vào:

Dòng 1: N, M.

N dòng tiếp theo: Ma trận A.

Đầu ra:

Số lượng ước số lớn nhất tìm được của tổng các vùng 5 ô (dấu cộng).

Ràng buộc:

1 <= N, M <= 500

1 <= A[i][j] <= 10^4

Tổng giá trị vùng 5 ô có thể lên tới 5*10^4.

Ví dụ 1:

Input:

3 3 
1 1 1 
1 10 1 
1 1 1

Output:

4 
(Giải thích: Ô giữa có tổng vùng là 1+1+10+1+1 = 14. Ước của 14 là 1, 2, 7, 14 -> 4 ước)

Ví dụ 2:

Input:

3 3 
2 2 2 
2 2 2 
2 2 2

Output:

4 
(Giải thích: Tổng là 10. Ước của 10 là 1, 2, 5, 10 -> 4 ước)

Cho ma trận nhị phân gồm N hàng và M cột chỉ bao gồm các số 0 và 1. Hãy đếm số lượng miền các số 1 trong ma trận, các ô số 1 được coi là cùng miền nếu chúng có chung đỉnh.

Ràng buộc: 1 ≤ N,M ≤ 50

Input 01:

3 3
1 0 1
0 0 1
1 1 0

Output 01:

2

Input 01:

8 8
1 1 0 1 1 1 1 0
0 1 1 1 0 0 0 1
1 1 0 0 0 0 1 1
0 1 0 1 0 0 1 1
1 0 0 1 0 0 0 1
0 1 0 1 1 1 1 0
0 0 0 0 1 0 1 1
1 0 0 0 0 0 0 0

Output 02:

2

Tèo khá thích chơi cờ vua và quân cờ mà Tèo yêu thích chính là quân Tịnh, bây giờ Tèo có một bàn cờ cỡ NxN, trên bàn cờ sẽ có những ô trống và có những ô có vật cản, nhiệm vụ của bạn là hãy xác định xem số lượng ô trên bàn cờ mà quân Tịnh có thế di chuyển tới, biết rằng nó có thể đi qua đi lại 1 ô trống nhiều lần và không thể đi vào ô có vật cản.

Bàn cờ gồm N hàng N cột, mỗi ô là số 1 Tương ứng với vật cản và ô số 0 tương ứng với ô trống. Ban đầu quân Tịnh năm ở vị trí hàng S và cột T và ô (S, T) là ô trống

Định dạng đầu vào:

• Dòng 1 là N, S, T

• N dòng tiếp theo mỗi dòng gồm N số

Ràng buộc:

~5 \leq N＜=20~

~0 \leq A[i][j] \leq 1~

Đầu ra:

In ra số lượng ô trên bàn cờ mà quân Tịnh có thể đến được

Ví dụ:

Input:

6 1 3
0 0 0 1 1 0
1 1 1 0 1 0
1 0 0 1 0 1
1 1 1 1 1 0
0 0 1 1 1 0
0 1 1 0 1 0

Output:

6

Tèo khá thích chơi cờ vua và quân cờ mà Tèo yêu thích chính là quân Xe, bây giờ Tèo có một bàn cờ cỡ NxN, trên bàn cờ sẽ có những ở trồng và có những ô có vật cản, nhiệm vụ của bạn là hãy xác định xem số lượng ô trên bàn cờ mà quân Xe có thế di chuyển tới, biết ràng nó có thế đi qua đi lại 1 ô trống nhiều lần và không thể đi vào ô có vật cản.

Bàn cờ gồm N hàng N cột, mỗi ô là số 1 tương ứng với vật cản và ô số 0 tương ứng với ô trồng. Ban đầu quân Xe năm ở vị trí hàng 5 và cột T và ô (5, T) là ô trống

Định dạng đầu vào:

• Dòng 1 là N, S, T

• N dòng tiếp theo mỗi dòng gồm N số

Ràng buộc:

~5 \leq N＜=20~

~0 \leq A[i][j] \leq 1~

Đầu ra:

In ra số lượng ô trên bàn cờ mà quân Xe có thể đến được

Ví dụ:

Input:

7 4 6
1 1 1 0 0 1 0
1 1 0 0 0 1 1
0 1 0 0 0 0 0
1 0 1 0 1 0 1
1 0 1 1 1 1 0
1 1 0 0 1 0 1
0 0 0 0 1 1 0

Output:

12

Cho bàn cờ vua cỡ N * N, các ô trên bàn cờ có giá trị là 0 hoặc 1. Một con mã xuất phát từ ô (s, t) và muốn di chuyến tới ô (u, v), con mã chỉ có thể di chuyển ở các ô mà tại ô đó có giá trị là 1 và nó có thế di chuyến qua lại 1 ô nhiều lần. Hãy xác định xem con mã có thế tìm được đường đi hay không, dữ liệu đảm bảo ô (s, t) và ô (u, v) đều có giá trị là 1.

Ràng buộc: 1 ≤ N,M ≤ 100; 1 ≤ s,t,u,v ≤ N; 0 ≤ A[i][j] ≤ 1;

In YES nếu con mã có thể tìm được đường đi, ngược lại in NO.

Input:

9
7 5 4 3
1 0 1 0 1 0 1 1 1
1 1 1 1 0 0 0 0 1
1 0 1 1 1 0 1 1 1
1 0 1 0 1 0 0 0 0
0 1 1 0 1 0 1 1 1
1 0 0 0 0 1 1 0 1
1 0 1 0 1 0 1 1 0
0 1 1 0 0 0 0 1 1
0 0 1 1 0 0 0 0 1

Output:

YES