Mảng 2 chiều
- Độ khó
- ★★★☆☆ Vừa
- Thời lượng
- Khoảng 90 phút
- Học trước
- Mảng 1 chiều, Vector
- Chủ đề
- ma trậnmảng 2 chiều
- Trạng thái
Kiến thức cơ bản
Mảng 2 chiều
Mảng 2 chiều (2D array), còn gọi là ma trận (matrix), là một bảng số gồm nhiều dòng và nhiều cột. Mỗi ô trong bảng được gọi bằng hai chỉ số: dòng i và cột j, viết là a[i][j]. Như mảng 1 chiều các chỉ chỉ số dòng và cột trong C++ đều bắt đầu từ 0.
Ví dụ một bảng có n = 3 dòng và m = 4 cột:
| Cột 0 | Cột 1 | Cột 2 | Cột 3 | |
|---|---|---|---|---|
| Dòng 0 | a[0][0] | a[0][1] | a[0][2] | a[0][3] |
| Dòng 1 | a[1][0] | a[1][1] | a[1][2] | a[1][3] |
| Dòng 2 | a[2][0] | a[2][1] | a[2][2] | a[2][3] |
Ô tô vàng ở dòng 1, cột 2 nên được viết là a[1][2] với quy tắc dòng trước, cột sau. Bảng trên có 12 ô chỉ số dòng từ 0 đến n-1 = 2, chỉ số cột từ 0 đến m-1 = 3.
Nếu mảng 1 chiều có một hàng và nhiều cột thì mảng 2 chiều chính là một mảng các mảng 1 chiều.
Đứng tại ô (i, j), một nhân vật trong game muốn bước sang 4 ô hàng xóm liền kề (Lên, Xuống, Trái, Phải) thì tọa độ thay đổi như sau:
- Đi lên (Up): Hàng giảm 1, cột giữ nguyên (i - 1, j).
- Đi xuống (Down): Hàng tăng 1, cột giữ nguyên (i + 1, j).
- Sang trái (Left): Hàng giữ nguyên, cột giảm 1 (i, j - 1).
- Sang phải (Right): Hàng giữ nguyên, cột tăng 1 (i, j + 1).
Khai báo, nhập xuất mảng 2 chiều
Để khai báo mảng, ta dùng một số cú pháp sau:
int a[100][100]; // mảng a tối đa 100 dòng, 100 cột
// mảng b có n dòng, m cột, mọi ô ban đầu là 0
vector<vector<int>> b(n, vector<int>(m));
// mảng c có n dòng, m cột, mọi ô khởi tạo là 5
vector<vector<int>> c(n, vector<int>(m, 5));
Để nhập mảng, ta đọc lần lượt từng ô, từ trái sang phải, từ trên xuống dưới:
for (int i = 0; i < n; ++i) // vòng ngoài: từng dòng i
for (int j = 0; j < m; ++j) // vòng trong: từng cột j của dòng i
cin >> a[i][j];
Ví dụ in mảng, hết một dòng thì xuống dòng:
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j)
cout << a[i][j] << " ";
cout << endl; // xuống dòng sau khi in xong dòng i
}
Đôi khi ta cần duyệt theo cột, khi đó chỉ cần đổi vai hai vòng lặp: vòng ngoài là cột j, vòng trong là dòng i.
Mảng vuông
Khi mảng có số dòng bằng số cột (n × n) ta gọi là mảng vuông. Mảng vuông có hai đường chéo:
- Đường chéo chính: đi từ góc trên trái xuống góc dưới phải, gồm các ô có chỉ số dòng bằng cột (i == j). Các ô nằm trên đường chéo chính có j > i, các ô nằm dưới đường chéo chính có j < i.
- Đường chéo phụ: đi từ góc trên phải xuống góc dưới trái, tổng chỉ số của dòng + cột = n - 1 (i + j == n - 1).
Luyện tập
Bài 1. Bảng điểm của lớp
Lớp 6A0 có n bạn, mỗi bạn làm m bài kiểm tra. Cô giáo ghi điểm vào một bảng gồm n dòng, m cột (mỗi dòng là điểm của một bạn). Bạn giúp hãy giúp cô:
- Tính tổng điểm của từng bạn.
- Với mỗi bài kiểm tra, điểm của cả lớp là bao nhiêu
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 100) n dòng tiếp theo, mỗi dòng gồm m số nguyên (0 ≤ điểm ≤ 10) | |
|---|---|---|
| Đầu ra | n dòng, dòng thứ i là tổng điểm của bạn ở dòng thứ i (i tính từ 0). Dòng thứ n+1: tổng điểm của m bài kiểm tra, cách nhau dấu cách. | |
| Test | Input | Output |
| 3 4 8 9 7 10 6 5 8 7 9 9 9 9 | 34 26 36 23 23 24 26 | |
Bài 2. Bức tường thành vững chãi
Một lâu đài cổ hình chữ nhật có kích thước n.m. Nhà vua muốn xây dựng lại toàn bộ bức tường bao quanh lâu đài (chính là tất cả các ô nằm ở rìa ngoài cùng). Hãy tính tổng chi phí gia cố bức tường bao này!
| Đầu vào | Dòng 1: hai số nguyên n, m (2 ≤ n, m ≤ 1000) n dòng tiếp theo, mỗi dòng gồm m số nguyên (0 ≤ a[i][j] ≤ 104) | |
|---|---|---|
| Đầu ra | Một số nguyên duy nhất là tổng giá trị các ô nằm trên viền ma trận | |
| Test | Input | Output |
| 3 4 1 2 3 4 5 1 2 6 7 8 9 0 | 40 | |
Bài 3. Hai đường chéo của bàn cờ
Cho một bảng vuông n.n. Đường chéo chính đi từ góc trên bên trái xuống góc dưới bên phải. Đường chéo phụ đi từ góc trên bên phải xuống góc dưới bên trái. Hãy tính tổng các số trên mỗi đường chéo.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 100). n dòng tiếp theo, mỗi dòng gồm n số nguyên (|a[i][j]| ≤ 1000). | |
|---|---|---|
| Đầu ra | Tổng đường chéo chính và đường chéo phụ, cách nhau dấu cách | |
| Test | Input | Output |
| 3 1 2 3 4 5 6 7 8 10 | 16 15 | |
Bài 4. Số lớn nhất, nhỏ nhất
Hãy tìm số nhỏ nhất và số lớn nhất trong ma trận n.m, sau đó liệt kê các vị trí xuất hiện của các phần tử này trong ma trận.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 100). n dòng tiếp theo, mỗi dòng gồm m số nguyên (|a[i][j]| ≤ 109). | |
|---|---|---|
| Đầu ra | Dòng đầu tiên in ra số nhỏ nhất trong ma trận, các dòng tiếp theo liệt kê các vị trí của số này trong ma trận. Dòng tiếp theo in ra số lớn nhất trong ma trận, các dòng tiếp theo liệt kê các chỉ số của số này trong ma trận. | |
| Test | Input | Output |
| 3 3 1 2 1 4 5 6 7 8 9 | 1 0 0 0 2 9 2 2 | |
Bài 5. Chiếc kính lúp dò bạn thân
Cho một bàn cờ n.m gồm các số nguyên. Bạn hãy đếm xem trong 4 ô lân cận (trên, dưới, trái, phải) của ô (r, c) có bao nhiêu ô có giá trị lớn hơn giá trị tại ô này.
| Đầu vào | Dòng 1: hai số nguyên n, m, r, c (1 ≤ n, m ≤ 500; 0 ≤ r < n; 0 ≤ c < m). n dòng tiếp theo, mỗi dòng gồm m số nguyên (|a[i][j]| ≤ 109). | |
|---|---|---|
| Đầu ra | In ra số lượng ô lân cận có giá trị lớn hơn ô a[r][c]. | |
| Test | Input | Output |
| 3 3 1 1 1 8 3 4 5 6 2 7 9 | 3 | |
Hướng dẫn: thay vì viết 4 câu lệnh if dài dòng, dân Lập trình thi đấu dùng Bộ mảng biến hình:
// Thứ tự: Lên, Xuống, Trái, Phải
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
// Duyệt 4 hàng xóm chỉ bằng 1 vòng lặp duy nhất:
for (int k = 0; k < 4; ++k) {
int u = i + dx[k]; // Tọa độ hàng mới
int v = j + dy[k]; // Tọa độ cột mới
// Kiểm tra xem có bị "ngã khỏi mép bản đồ" không!
if (u >= 0 && u < n && v >= 0 && v < m) {
// xử lý ô (u, v) là hàng xóm hợp lệ
}
}
Bài 6. Kho báu lớn nhất
Bản đồ kho báu là một bảng n dòng, m cột, mỗi ô ghi số lượng vàng. Hãy tìm ô có nhiều vàng nhất. Nếu có nhiều ô cùng nhiều nhất, chọn ô gặp đầu tiên khi đọc từ trên xuống dưới, mỗi dòng đọc từ trái sang phải.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 100). n dòng tiếp theo, mỗi dòng gồm m số nguyên (0 ≤ số vàng ≤ 1000). | |
|---|---|---|
| Đầu ra | Ba số cách nhau bởi dấu cách: số vàng lớn nhất, chỉ số dòng và chỉ số cột của ô đó (tính từ 0). | |
| Test | Input | Output |
| 3 4 5 2 9 1 7 9 3 4 6 8 2 0 | 9 0 2 | |
Bài 7. Xoay bảng điểm
Cô giáo muốn đổi bảng điểm: dòng thứ i của bảng cũ sẽ trở thành cột thứ i của bảng mới. Bạn hãy in ra bảng mới nhé! (Phép biến đổi này gọi là chuyển vị)
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 100). n dòng tiếp theo, mỗi dòng gồm m số nguyên (|a[i][j]| ≤ 1000). | |
|---|---|---|
| Đầu ra | m dòng, mỗi dòng gồm n số cách nhau bởi dấu cách: bảng sau khi chuyển vị | |
| Test | Input | Output |
| 2 3 1 2 3 4 5 6 | 1 4 2 5 3 6 | |
Bài 8. Snake
Hãy in các phần tử thuộc ma trận vuông n.n theo hình con rắn. Với chỉ số hàng tính từ 0, hàng chẵn in từ trái qua phải, hàng lẻ in từ phải qua trái.
| Đầu vào | Dòng 1: số nguyên dương n (1 ≤ n ≤ 100). n dòng tiếp mỗi dòng gồm n số nguyên |a[i][j]| ≤ 109. | |
|---|---|---|
| Đầu ra | In ra ma trận theo yêu cầu. | |
| Test | Input | Output |
| 3 1 2 3 4 5 6 7 8 9 | 1 2 3 6 5 4 7 8 9 | |
Bài tập tự luyện
Bài 1. Bàn cờ X và O
Hãy vẽ một bàn cờ gồm n dòng, m cột bằng hai ký tự X và O. Ô ở góc trên bên trái là X, hai ô kề nhau (trên, dưới, trái, phải) luôn khác ký tự.
| Đầu vào | Một dòng gồm hai số nguyên n, m (1 ≤ n, m ≤ 100) | |
|---|---|---|
| Đầu ra | n dòng, mỗi dòng gồm m ký tự X hoặc O, không có dấu cách | |
| Test | Input | Output |
| 3 4 | XOXO OXOX XOXO | |
Bài 2. Hoán vị hàng, cột
Hãy hoán vị các phần tử trên 2 hàng, 2 cột của ma trận vuông kích thước n.n.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 200). n dòng tiếp theo, mỗi dòng gồm n số nguyên (|a[i]| ≤ 109). Dòng tiếp theo là 2 chỉ số u, v (tính từ 0) cần hoán vị. | |
|---|---|---|
| Đầu ra | In ra ma trận sau khi hoán vị 2 hàng u, v Cách một dòng, in ra ma trận sau khi hoán vị 2 cột u, v | |
| Test | Input | Output |
| 3 1 2 3 4 5 6 7 8 9 0 2 | 7 8 9 4 5 6 1 2 3 3 2 1 6 5 4 9 8 7 | |
Bài 3. Hình vuông kỳ diệu
Một bảng vuông n.n được gọi là kỳ diệu nếu tổng của mọi dòng, tổng của mọi cột, tổng đường chéo chính và tổng đường chéo phụ đều bằng nhau. Hãy kiểm tra xem bảng cho trước có kỳ diệu không.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 100). n dòng tiếp theo, mỗi dòng gồm n số nguyên (|a[i][j]| ≤ 1000). | |
|---|---|---|
| Đầu ra | In YES nếu bảng kỳ diệu, ngược lại in NO | |
| Test | Input | Output |
| 3 2 7 6 9 5 1 4 3 8 | YES | |
| 3 1 2 3 4 5 6 7 8 9 | NO | |
Bài 4. Bảng số đối xứng
Một bảng vuông gọi là đối xứng nếu đặt một chiếc gương dọc theo đường chéo chính thì hình phản chiếu trùng khít với bảng gốc. Hãy kiểm tra bảng cho trước.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 100). n dòng tiếp theo, mỗi dòng gồm n số nguyên (|a[i][j]| ≤ 1000). | |
|---|---|---|
| Đầu ra | In YES nếu bảng đối xứng, ngược lại in NO | |
| Test | Input | Output |
| 3 1 2 3 2 5 6 3 6 9 | YES | |
| 3 1 2 3 4 5 6 7 8 9 | NO | |
Hướng dẫn: bảng đối xứng tức là a[i][j] = a[j][i] với mọi ô.
Bài 5. Tam giác Pascal
Tam giác Pascal có dòng 0 chỉ gồm số 1. Mỗi dòng bắt đầu và kết thúc bằng số 1, còn các số ở giữa bằng tổng của hai số đứng ngay phía trên nó (trên-trái và trên-phải). Hãy in n dòng đầu tiên của tam giác.
| Đầu vào | Một số nguyên n (1 ≤ n ≤ 20). | |
|---|---|---|
| Đầu ra | n dòng, dòng thứ i (tính từ 0) có i + 1 số cách nhau bởi dấu cách. | |
| Test | Input | Output |
| 5 | 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 | |
Bài 6. Đỉnh núi
Một vùng núi được vẽ thành bảng n dòng, m cột, mỗi ô ghi độ cao. Một ô được gọi là đỉnh núi nếu độ cao của nó lớn hơn độ cao của tất cả các ô kề bên (trên, dưới, trái, phải). Ô nằm ở mép bảng chỉ so sánh với những ô kề bên có trong bảng. Hãy đếm số đỉnh núi.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 1000) n dòng tiếp theo, mỗi dòng gồm m số nguyên (0 ≤ độ cao ≤ 109) | |
|---|---|---|
| Đầu ra | Số lượng đỉnh núi | |
| Test | Input | Output |
| 3 4 1 2 1 3 2 5 2 1 1 2 1 4 | 3 | |
Bài 7. Game Dò Mìn
Bản đồ mìn kích thước n.m gồm các ký tự: ký tự * đại diện cho quả mìn, ký tự . đại diện cho ô an toàn. Hãy tạo ra bảng số cho trò chơi: thay thế mỗi ô an toàn . bằng một chữ số biểu thị số lượng quả mìn nằm trong 8 ô bao quanh nó, các ô có mìn * giữ nguyên.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 100) n dòng tiếp theo, mỗi dòng gồm m kí tự * hoặc . | |
|---|---|---|
| Đầu ra | In ra bảng kích thước n.m sau khi tính toán | |
| Test | Input | Output |
| 3 3 * . . . . . . . * | * 1 0 1 2 1 0 1 * | |
Bài 8. Ma trận xoắn ốc
Xây dựng ma trận xoắn ốc cấp n.
| Đầu vào | Số nguyên dương n (1 ≤ n ≤ 100) là cấp của ma trận xoáy ốc. | |
|---|---|---|
| Đầu ra | In ra ma trận xoáy ốc cấp n. | |
| Test | Input | Output |
| 3 | 1 2 3 8 9 4 7 6 5 | |