Tìm vị trí số 25 trong ma trận

Nguồn: CLUE OJ Độ khó: Dễ Mảng 2 chiều Duyệt ma trận

Đề bài

Cho mảng hai chiều $a$ gồm $m$ dòng và $n$ cột. Hãy tìm và in ra chỉ số (dòng, cột) của tất cả các phần tử có giá trị bằng $25$.

Dòng và cột được đánh số từ $0$: dòng trên cùng là dòng $0$, cột bên trái là cột $0$.

Dữ liệu vào:

• Dòng đầu tiên gồm hai số nguyên dương $m, n$.
• $m$ dòng tiếp theo, mỗi dòng gồm $n$ số nguyên là một dòng của mảng $a$.

Kết quả:

• Mỗi dòng in ra hai số $i$ $j$ (cách nhau bởi dấu cách) là chỉ số dòng và chỉ số cột của một phần tử bằng $25$.
• Các cặp chỉ số in theo thứ tự duyệt mảng: lần lượt từng dòng từ trên xuống, trong mỗi dòng từ trái sang phải.
• Nếu mảng không có phần tử nào bằng $25$, in ra -1.

Giới hạn:

• $1 \le m, n \le 500$
• $0 \le a[i][j] \le 10^9$

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

2 4
20 24 25 26
25 27 25 26

Ví dụ 1 – output

0 2
1 0
1 2

Ví dụ 2 – input

2 3
1 2 3
4 5 6

Ví dụ 2 – output

-1

• Ví dụ 1: số $25$ nằm ở dòng $0$ cột $2$, dòng $1$ cột $0$ và dòng $1$ cột $2$.
• Ví dụ 2: không có số $25$ nào nên in -1.

Nguồn: phỏng theo bài "MỞ RỘNG TH4" – vinhdinhcoder.net (chủ đề Mảng 2 chiều).

Lời mở đầu

Bài mở màn của chương mảng 2 chiều: đọc một ma trận vào mảng a[i][j] rồi duyệt hai vòng for lồng nhau để tìm các ô bằng 25. Điều quan trọng là thứ tự duyệt (dòng trước, cột sau) và chỉ số bắt đầu từ 0. Ghi chú: đề gốc không nói nếu không có số 25 thì in gì, mình chốt in -1; đề gốc dùng tệp, trên CLUE OJ đọc bàn phím và in màn hình; đề cũng chưa có giới hạn giá trị nên mình bổ sung $0 \le a[i][j] \le 10^9$.

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

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

Bộ test20 testÝ tưởnghai vòng for lồng nhauLời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau. Mọi test có $1 \le m, n \le 500$.

Test	Nội dung kiểm tra
1–2	Hai ví dụ của đề (có và không có số 25)
3–10	Ma trận nhỏ: 1 ô, một dòng, một cột, toàn số 25, số 25 ở góc, các số "na ná" như 250, 52, 125
11–20	Ma trận lớn tới 500 × 500, có test toàn số 25 (250 000 dòng kết quả), test không có số 25, ma trận không vuông – đọc nhầm $m, n$ hay duyệt theo cột sẽ sai

Ý tưởngDuyệt từng dòng, trong mỗi dòng duyệt từng cột

Ma trận $m$ dòng $n$ cột được lưu trong mảng 2 chiều a[i][j]: i là chỉ số dòng ($0 \to m - 1$), j là chỉ số cột ($0 \to n - 1$).

Vòng ngoài chạy i, vòng trong chạy j: như vậy ta đi hết dòng 0 từ trái sang phải, rồi xuống dòng 1, ... – đúng thứ tự đề yêu cầu in. Gặp ô nào bằng 25 thì in ngay i j.

Biến cờ

Để biết có phải in -1 hay không, ta dùng biến bool co = false; mỗi khi gặp số 25 thì gán co = true. Duyệt xong mà co vẫn là false nghĩa là không có số 25 nào.

Em nhập ma trận (các dòng cách nhau bởi dấu ;) rồi bấm Tiếp để xem thứ tự duyệt từng ô:

Ma trận =

Ví dụ nhanh:

Lời giảiHai vòng for và một biến cờ

Mảng khai báo toàn cục a[505][505] (dư một chút so với 500). Vì có thể phải in tới 250 000 dòng, mình dùng "\n" thay cho endl và tắt đồng bộ ios::sync_with_stdio(false) để in nhanh.

C++▶ Chạy tay từng dòng codeĐọc ma trận rồi duyệt dòng → cột, gặp 25 thì in chỉ số.

Dữ liệu vào (stdin) – sửa thoải mái2 4 20 24 25 26 25 27 25 26

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Thứ tự vòng lặp quyết định thứ tự in: vòng ngoài là dòng i, vòng trong là cột j. Đổi ngược hai vòng thì kết quả in theo từng cột – sai thứ tự.
2. Chỉ số trong C++ và Python vốn bắt đầu từ 0 nên in thẳng i, j; không cộng thêm 1.
3. Bản Python đọc toàn bộ dữ liệu một lần bằng sys.stdin.read().split() và gom kết quả vào danh sách rồi in một lần cho nhanh.

Không gian$O(m \cdot n)$

Thời gian$O(m \cdot n)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.049s. Bản Python đúng 20/20 test, chạy lâu nhất 0.189s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
In chỉ số tính từ 1 (i + 1, j + 1)	3/20	sai test 1, 3, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20
Vòng ngoài là cột, vòng trong là dòng	11/20	sai test 1, 5, 8, 9, 11, 12, 16, 17, 19
Đọc nhầm thứ tự cin >> n >> m	7/20	sai test 1, 5, 6, 7, 8, 9, 10, 14, 15, 16, 17, 18, 19
Quên in -1 khi không có số 25	17/20	sai test 2, 4, 13

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.049s	Full điểm
	Python	20/20	0.189s	Full điểm
Chỉ số từ 1	C++	3/20	–	Mất 17 test
Duyệt cột trước	C++	11/20	–	Mất 9 test
Đọc nhầm m, n	C++	7/20	–	Mất 13 test
Quên -1	C++	17/20	–	Mất 3 test

Ghi chú của mình: với mảng 2 chiều, hãy luôn tự hỏi: biến nào là dòng, biến nào là cột, và vòng nào ở ngoài. Hai câu hỏi này quyết định gần như mọi lỗi sai ở chương nà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 😇