Đếm số phần tử cực đại trong ma trận

Nguồn: Bài tập chương Ma trận (bài 342) Độ khó: Dễ Ma trận Duyệt lân cận Mảng hướng dx, dy

Đề bài

Đếm số lượng phần tử cực đại trong ma trận các số thực. Một phần tử được gọi là cực đại khi nó lớn hơn các phần tử xung quanh (tức là lớn hơn tất cả các phần tử lân cận với nó, kể cả các phần tử nằm chéo góc).

Dữ liệu vào và kết quả (mình bổ sung để các bạn chạy thử): bài tập gốc là một bài trong chương ma trận, chỉ yêu cầu viết hàm int CountMaximaInMatrix(double a[][MAX], int rows, int colums) trả về số phần tử cực đại. Để tiện kiểm tra, trong bài này mình quy ước:

• Dòng đầu gồm 2 số nguyên $rows$, $colums$ $(1 \le rows, colums \le 100)$: số dòng và số cột của ma trận.
• $rows$ dòng tiếp theo, mỗi dòng gồm $colums$ số thực là các phần tử của ma trận.
• Kết quả: một số nguyên là số lượng phần tử cực đại trong ma trận.

Ví dụ 1 – input

3 3
1 2 3
4 5 6
7 8 9

Ví dụ 1 – output

1

Ví dụ 2 – input

3 4
1 5 2 8
3 2 4 1
9 1 3 7

Ví dụ 2 – output

4

Lời mở đầu

Bài này là một bạn học viên nhắn hỏi mình. Những dạng bài xét các phần tử lân cận thế này có cách code rất gọn, nên mình viết lại thành bài giải để anh em tham khảo nhé. Hy vọng mang đến được giá trị cho các bạn 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Giải thích ví dụ. Với ma trận ở ví dụ 1, số $5$ ở giữa phải kiểm tra hết xung quanh, cả các đường chéo luôn: xung quanh một số có tối đa 8 số. Còn như số $1$ ở góc thì chỉ có 3 số xung quanh thôi ($2$, $4$, $5$); các số nằm ở biên (như số $2$) thì có 5 số xung quanh. Trong ma trận này chỉ có số $9$ là lớn hơn tất cả các số xung quanh nó ($5$, $6$, $8$) ⇒ đáp án là $1$.

Ở ví dụ 2 có 4 phần tử cực đại: $5$ (lớn hơn $1, 2, 3, 2, 4$), $8$ (lớn hơn $2, 4, 1$), $9$ (lớn hơn $3, 2, 1$) và $7$ (lớn hơn $4, 1, 3$). Số $4$ ở giữa thì không phải vì nó nhỏ hơn $5$, $8$, $7$.

Cách làm "nguyên đống hàm" của bạn học viên

Bạn ấy chia hết các trường hợp đặc biệt ra thành từng hàm riêng: kiểm tra phần tử ở giữa, ở biên trên, biên trái, biên phải, biên dưới, rồi 4 góc trái trên, phải trên, trái dưới, phải dưới... Code dài hơn 200 dòng, chỉnh qua chỉnh lại còn dài thêm nữa, gần 500 dòng 😅. Cách đó vẫn đúng nhưng rất dễ sai sót và khó sửa. Không ai mất công chia từng cái như thế cả, mình chỉ cách viết gọn ngay dưới đây.

Lộ trình lời giải, bấm vào để nhảy tới:

Cách 1Duyệt 8 ô lân cận bằng 2 mảng dx, dy · O(rows · colums)

Cách 1Duyệt 8 ô lân cận bằng 2 mảng dx, dy – O(rows·colums)

Ta sẽ tạo 2 mảng dx và dy:

int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

• dx là mảng ứng với chỉ số dòng, dy là mảng ứng với chỉ số cột.
• Mỗi mảng có 8 phần tử, là số lượng phần tử lân cận tối đa.

Vậy 2 mảng đó làm sao tính được sự chênh lệch, lúc $-1$ lúc $0$ lúc $1$ là dựa vào đâu? Các bạn nhìn nhé, xung quanh phần tử a[i][j] có tối đa 8 phần tử lân cận:

• Trái trên, ngay bên trên, phải trên: tất cả đều nằm ở dòng bé hơn 1 so với dòng hiện tại, thế nên khởi đầu mảng dx là 3 số: $-1, -1, -1$.
• Bên trái, bên phải: tất cả đều cùng dòng với dòng hiện tại, thế nên tiếp theo sẽ là 2 số $0, 0$.
• Trái dưới, ngay bên dưới, phải dưới: tất cả đều nằm ở dòng lớn hơn 1 so với dòng hiện tại, thế nên tiếp theo sẽ là 3 số: $1, 1, 1$.

Mảng dy làm tương tự với cột: bên trái là $-1$, cùng cột là $0$, bên phải là $1$. Cặp (dx[k], dy[k]) chính là độ lệch (dòng, cột) của lân cận thứ $k$ so với a[i][j]:

k = 0(−1, −1)	k = 1(−1, 0)	k = 2(−1, 1)
k = 3(0, −1)	a[i][j](0, 0)	k = 4(0, 1)
k = 5(1, −1)	k = 6(1, 0)	k = 7(1, 1)

Hình: 8 ô lân cận của a[i][j] và cặp (dx[k], dy[k]) tương ứng.

Thì lúc này, tại vị trí phần tử a[i][j] đang xét trong ma trận, từ index dòng $i$ ta chỉ cần lấy i + dx[k] với $k$ lần lượt là từng index phần tử trong mảng dx, thế là ta đã ra được vị trí index dòng của các phần tử lân cận; làm tương tự với cột j + dy[k]. Thay vì cả trăm dòng xét từng trường hợp thì giờ chỉ cần 2 mảng 😃:

for(int i = 0; i < rows; ++i)
{
    for(int j = 0; j < cols; ++j)
    {
        // với mỗi phần tử a[i][j] trong ma trận, ta đi xét các phần tử kề với nó bằng cách:
        for(int k = 0; k < 8; ++k)
        {
            int idx_row = i + dx[k];
            int idx_col = j + dy[k];
            if(idx_row >= 0 && idx_row < rows && idx_col >= 0 && idx_col < cols)
            {
                // lúc này a[idx_row][idx_col] là các phần tử kề với a[i][j]
            }
        }
    }
}

Đơn giản vậy thôi, các bạn làm kinh nghiệm với mấy dạng bài xét các phần tử kề kiểu này nhé 😃. Áp dụng vào bài đếm phần tử cực đại:

• Vòng lặp for k là để xét qua tất cả các phần tử lân cận với a[i][j].
• Kiểm tra những index hợp lệ (câu if có 4 điều kiện): bởi ví dụ những phần tử ở góc thì đâu đủ 8 phần tử lân cận xung quanh đúng không? Thành ra chỉ xét những index lân cận hợp lệ, tức là nằm trong ma trận. Nhờ vậy ta không cần tách riêng trường hợp góc hay biên nữa, đã xét cả đường chéo luôn.
• Đề yêu cầu đếm các phần tử cực đại, tức là phải lớn hơn tất cả các phần tử lân cận nó. Nên chỉ cần có trường hợp nào mà a[i][j] bé hơn hoặc bằng một phần tử lân cận hợp lệ thì lập tức cập nhật cờ hiệu check = false và thoát ra.
• Sau cùng chỉ cần kiểm tra biến cờ hiệu check: nếu vẫn là true tức là không có trường hợp nào mà a[i][j] bị $\le$ phần tử lân cận bất kỳ của nó, thì lúc này hiểu rằng a[i][j] chính là 1 cực đại thỏa mãn ⇒ count++ để đếm. Cuối hàm return count; là đáp án bài toán cần.

Ý chính

Với mỗi ô $(i, j)$, duyệt $k = 0..7$, ô lân cận là $(i + dx[k],\ j + dy[k])$; bỏ qua ô nằm ngoài ma trận; gặp ô lân cận nào $\ge a[i][j]$ thì $a[i][j]$ không phải cực đại.

Các bạn nhập ma trận rồi bấm Tiếp để xem từng ô được so với các lân cận của nó (ô viền nét đứt là vị trí nằm ngoài ma trận, bị bỏ qua):

Ma trận (mỗi dòng cách nhau bởi dấu ;)

Ví dụ nhanh:

Source code để các bạn tham khảo. Hàm xử lý chính CountMaximaInMatrix chỉ có khoảng 30 dòng, so với gần 500 dòng chia trường hợp 😆. Mình giữ nguyên tên hàm và tên biến colums như bài tập gốc, chỉ thêm hàm main để đọc dữ liệu và chạy thử:

#include <iostream>
using namespace std;
#define MAX 100

int CountMaximaInMatrix(double a[][MAX], int rows, int colums)
{
    int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
    int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

    int count = 0;
    for(int i = 0; i < rows; ++i)
    {
        for(int j = 0; j < colums; ++j)
        {
            // với mỗi phần tử a[i][j], ta đi xét các phần tử kề với nó
            bool check = true;
            for(int k = 0; k < 8; ++k)
            {
                int idx_row = i + dx[k];
                int idx_col = j + dy[k];
                if(idx_row >= 0 && idx_row < rows && idx_col >= 0 && idx_col < colums)
                {
                    // lúc này a[idx_row][idx_col] là phần tử kề với a[i][j]
                    if(a[i][j] <= a[idx_row][idx_col])
                    {
                        check = false;
                        break;
                    }
                }
            }
            if(check == true)
                count++;
        }
    }
    return count;
}

double a[MAX][MAX];

int main()
{
    int rows, colums;
    cin >> rows >> colums;
    for(int i = 0; i < rows; ++i)
        for(int j = 0; j < colums; ++j)
            cin >> a[i][j];
    cout << CountMaximaInMatrix(a, rows, colums);
    return 0;
}

def count_maxima_in_matrix(a, rows, colums):
    dx = [-1, -1, -1, 0, 0, 1, 1, 1]
    dy = [-1, 0, 1, -1, 1, -1, 0, 1]

    count = 0
    for i in range(rows):
        for j in range(colums):
            # với mỗi phần tử a[i][j], ta đi xét các phần tử kề với nó
            check = True
            for k in range(8):
                idx_row = i + dx[k]
                idx_col = j + dy[k]
                if 0 <= idx_row < rows and 0 <= idx_col < colums:
                    # lúc này a[idx_row][idx_col] là phần tử kề với a[i][j]
                    if a[i][j] <= a[idx_row][idx_col]:
                        check = False
                        break
            if check:
                count += 1
    return count


data = open(0).read().split()
rows, colums = int(data[0]), int(data[1])
vals = [float(x) for x in data[2:2 + rows * colums]]
a = [vals[i * colums:(i + 1) * colums] for i in range(rows)]
print(count_maxima_in_matrix(a, rows, colums))

Khung chạy tay dưới đây chạy đúng từng dòng của code C++ ở trên, các bạn suy ngẫm thử chạy tay sẽ thấy ngay vì sao đường chéo cũng đã được xét:

C++▶ Chạy tay từng dòng codeVới mỗi ô a[i][j], duyệt 8 lân cận (i + dx[k], j + dy[k]); gặp lân cận hợp lệ ≥ a[i][j] thì check = false.

Dữ liệu vào (stdin) – sửa thoải mái2 3 1 5 2 3 2 4

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3#define MAX 100

4

5int CountMaximaInMatrix(double a[][MAX], int rows, int colums)

6{

7 int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};

8 int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

9

10 int count = 0;

11 for(int i = 0; i < rows; ++i)

12 {

13 for(int j = 0; j < colums; ++j)

14 {

15 // với mỗi phần tử a[i][j], ta đi xét các phần tử kề với nó

16 bool check = true;

17 for(int k = 0; k < 8; ++k)

18 {

19 int idx_row = i + dx[k];

20 int idx_col = j + dy[k];

21 if(idx_row >= 0 && idx_row < rows && idx_col >= 0 && idx_col < colums)

22 {

23 // lúc này a[idx_row][idx_col] là phần tử kề với a[i][j]

24 if(a[i][j] <= a[idx_row][idx_col])

25 {

26 check = false;

27 break;

28 }

29 }

30 }

31 if(check == true)

32 count++;

33 }

34 }

35 return count;

36}

37

38double a[MAX][MAX];

39

40int main()

41{

42 int rows, colums;

43 cin >> rows >> colums;

44 for(int i = 0; i < rows; ++i)

45 for(int j = 0; j < colums; ++j)

46 cin >> a[i][j];

47 cout << CountMaximaInMatrix(a, rows, colums);

48 return 0;

49}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: ngoài ma trận ra chỉ dùng thêm 2 mảng 8 phần tử và vài biến: $O(1)$.
• Thời gian: mỗi ô xét tối đa 8 lân cận: $O(8 \cdot rows \cdot colums) = O(rows \cdot colums)$.

Không gian$O(1)$

Thời gian$O(rows \cdot colums)$

Kỹ thuật này có tên không?

Bạn học viên có hỏi mình cái này có tên kỹ thuật không, hay chỉ là cách để xét các phần tử kế bên. Nó là một cách để xét các phần tử lân cận dựa theo chỉ số index dòng và cột: tạo 2 mảng dx, dy lưu lại sự chênh lệch index dòng và cột so với phần tử hiện tại, rồi duyệt vòng lặp lấy index hiện tại cộng với sự chênh lệch đó, index nào hợp lệ thì phần tử tại đó chính là phần tử lân cận. Mình không biết đây có phải là một kỹ thuật có tên sẵn hay không, nhưng thường gặp những dạng bài này thì mình hay làm như thế 😃. Các bài quân hậu, điểm yên ngựa trên ma trận hay các bài loang (BFS/DFS) trên lưới cũng dùng y chang ý này; muốn xét 4 hướng thì chỉ cần đổi 2 mảng còn 4 phần tử.

Ma trận 1 × 1

Nếu ma trận chỉ có 1 phần tử thì nó không có lân cận nào, check vẫn giữ true nên code đếm nó là 1 cực đại (lớn hơn "tất cả" lân cận, mà không có lân cận nào). Đề không nói rõ trường hợp này, các bạn để ý nếu thầy cô có quy ước khác.

Ghi chú của mình: code C++ và Python đã được kiểm tra với 500 ma trận ngẫu nhiên (kích thước tới 6 × 6, một nửa là số nguyên nhỏ để có nhiều số bằng nhau, một nửa là số thực), so với code vét cạn liệt kê trực tiếp các ô xung quanh – khớp hết. Với ma trận $100 \times 100$ thì cả 2 bản chạy tức thì (dưới 0.05 giây).

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇