I. In-Class Exercises

Programming Exercises

1. Matrix Addition: L2201
2. Image Rotation: L2202
3. Image Blur Processing: L2203

II. Knowledge Summary

✨ Core Concepts of Multi-Dimensional Arrays

When learning one-dimensional arrays, we compared arrays to a row of numbered lockers, where a single index can locate any locker. But if the data naturally has a "row and column" structure — such as a chessboard, a grade sheet, or a pixel image — using a single row of lockers is not intuitive enough.

A multi-dimensional array is an array of arrays, used to store matrices, tables, and other multi-dimensional data. You can think of a two-dimensional array as a table with rows and columns (or seats in a classroom), where you need two indices — "which row, which column" — to identify a position.

The relationship between different dimensional arrays is as follows:

• 2D array: An array of 1D arrays (table)
• 3D array: An array of 2D arrays (multiple layers of tables, like multiple spreadsheets)
• 4D array: An array of 3D arrays
• And so on...

This lesson focuses mainly on two-dimensional arrays, the most commonly used multi-dimensional arrays in competitive programming. Three-dimensional and higher-dimensional arrays follow the same principles, just with more indices.

✨ Defining Multi-Dimensional Arrays

The syntax for defining multi-dimensional arrays is as follows:

type arrayName[size1][size2]...[sizeN];

Below are examples of defining arrays of different dimensions:

int arr2[2][3]; // Define a 2D array: 2 one-dimensional arrays of size 3
int arr3[4][2][3]; // Define a 3D array: 4 two-dimensional arrays, each with 2 one-dimensional arrays of size 3
int arr4[5][4][2][3]; // Define a 4D array: 5 three-dimensional arrays, each with 4 two-dimensional arrays

✨ Initializing Multi-Dimensional Arrays

Sequence Initialization

Using {} to initialize an array must be done at the time of definition. If data is provided inside {}, elements are assigned in order, and unfilled portions are set to 0.

1#include <iostream>
2using namespace std;
3
4int main() {
5    // Define a 2x3 two-dimensional array with direct initialization
6    // This means the 2D array contains 2 one-dimensional arrays of size 3
7    // Each row is the initialization data for one 1D array
8    int arr[2][3] = {
9        {1, 2, 3},  // first row
10        {4, 5, 6}   // second row
11    };
12    return 0;
13}

1#include <iostream>
2using namespace std;
3
4int main() {
5    // Define a 2x2x3 three-dimensional array with direct initialization
6    // This means the 3D array contains 2 two-dimensional arrays,
7    // each with 2 one-dimensional arrays of size 3
8    // Each row is the initialization data for one 1D array
9    int arr[2][2][3] = {
10        {
11            {1, 2, 3},  // layer 1, row 1
12            {4, 5, 6}   // layer 1, row 2
13        },
14        {
15            {7, 8, 9},  // layer 2, row 1
16            {10, 11, 12} // layer 2, row 2
17        }
18    };
19    return 0;
20}

fill_n Initialization

Requires the <algorithm> header. Can be used to assign values to an array at any point in the program, setting all elements to a specific value. fill_n requires three arguments: the address of the first element, the number of elements, and the initialization value (which can be any value).

1#include <iostream>
2#include <algorithm>
3using namespace std;
4
5int main () {
6    int arr[2][3];
7    fill_n(&arr[0][0], 2 * 3, -1);
8    return 0;
9}

memset Initialization

memset is a C-style initialization method that can be used to assign values to an array at any point, setting all elements to a specific value.

memset requires three arguments: the array name, the initialization value, and the array size.

The initialization value is typically expressed in hexadecimal. Common values are:

• 0: set all to zero
• -1: set all to -1
• 0x3f: represents a large integer (approximately 1,061,109,567)
• 0x7f: represents an integer close to the maximum value of int

Note that the array size is not the number of values stored in the array, but the memory size in bytes, typically obtained using sizeof(arr).

1#include <iostream>
2#include <algorithm>
3using namespace std;
4
5int arr[105][105];
6
7int main () {
8    memset(arr, 0, sizeof(arr));
9    memset(arr, 1, sizeof(arr));
10    memset(arr, -1, sizeof(arr));
11    memset(arr, 0x3f, sizeof(arr));
12    memset(arr, 0x7f, sizeof(arr));
13    return 0;
14}

Ways to Initialize an Array to All Zeros

Here is a summary of common methods to initialize a 2D array to all zeros:

arr[2][3] = {};
arr[2][3] = {0};
arr[2][3] = {{}, {}};
fill_n(&arr[0][0], 2 * 3, 0);
memset(arr, 0, sizeof(arr));

✨ Accessing Multi-Dimensional Array Elements

We use the form arrayName[index1][index2][...] to access array elements. This can be used to get the value at a given index or to assign a value to that position.

1#include <iostream>
2using namespace std;
3
4int main() {
5    // Define a 2x3 two-dimensional array
6    int arr[2][3] = {
7        {1, 2, 3},  // first row
8        {4, 5, 6}   // second row
9    };
10
11    // Access and output elements of the 2D array
12    for (int i = 0; i < 2; ++i) {
13        for (int j = 0; j < 3; ++j) {
14            cout << arr[i][j] << " ";
15        }
16        cout << endl;
17    }
18
19    return 0;
20}

1#include <iostream>
2using namespace std;
3
4int main() {
5    // Define a 2x3x4 three-dimensional array
6    int arr[2][3][4] = {
7        {
8            {1, 2, 3, 4},
9            {5, 6, 7, 8},
10            {9, 10, 11, 12}
11        },
12        {
13            {13, 14, 15, 16},
14            {17, 18, 19, 20},
15            {21, 22, 23, 24}
16        }
17    };
18
19    // Access and output elements of the 3D array
20    for (int i = 0; i < 2; ++i) {
21        for (int j = 0; j < 3; ++j) {
22            for (int k = 0; k < 4; ++k) {
23                cout << arr[i][j][k] << " ";
24            }
25            cout << endl;
26        }
27        cout << endl;
28    }
29
30    return 0;
31}

Key points when accessing array elements:

1. Indices start from 0 and end at array size - 1. That is, if the array has n elements, the first element has index 0 and the last has index n - 1
2. Array indices cannot be negative. When using operations like arr[i-1], always check that i-1 is greater than or equal to 0
3. Array indices must not go out of bounds. If the array has n elements, do not use an index exceeding n - 1. When using operations like arr[i+1], always check that i+1 is less than n
4. The compiler will not report errors for out-of-bounds array access, but the program will produce errors at runtime, so use indices carefully

✨ Execution Examples for Multi-Dimensional Arrays

The following examples illustrate how two-dimensional arrays are stored in memory and how operations work.

Example 1: Memory Layout of a 2D Array

int arr[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
};

Although we visualize a 2D array as a "table", in memory it is stored contiguously row by row:

Logical view (table):

+---+---+---+
| 1 | 2 | 3 |  row 0
+---+---+---+
| 4 | 5 | 6 |  row 1
+---+---+---+

Actual storage in memory (contiguous):

+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 |
+---+---+---+---+---+---+
[0][0]  [0][1]  [0][2]  [1][0]  [1][1]  [1][2]

The position of arr[i][j] in memory = base address + (i * number_of_columns + j) * sizeof(int)

Example 2: Matrix Transpose Execution Process

Transposing a 2x3 matrix into a 3x2 matrix, i.e., swapping rows and columns:

arr[2][3]:

+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+

result[3][2]:

1+---+---+
2| 1 | 4 |
3+---+---+
4| 2 | 5 |
5+---+---+
6| 3 | 6 |
7+---+---+

The core transpose operation: result[j][i] = arr[i][j]

1arr[0][0]=1 -> result[0][0]=1
2arr[0][1]=2 -> result[1][0]=2
3arr[0][2]=3 -> result[2][0]=3
4arr[1][0]=4 -> result[0][1]=4
5arr[1][1]=5 -> result[1][1]=5
6arr[1][2]=6 -> result[2][1]=6

Example 3: Effects of Different Initialization Methods

int arr[2][3] = {};           -> all zeros: {{0,0,0},{0,0,0}}
int arr[2][3] = {{1,2},{3}};  -> partial initialization: {{1,2,0},{3,0,0}}
fill_n(&arr[0][0], 6, -1);    -> all -1: {{-1,-1,-1},{-1,-1,-1}}
memset(arr, 0x3f, sizeof(arr)); -> all large numbers: approximately 1061109567

✨ Problem-Solving Steps for Multi-Dimensional Arrays

General steps for solving problems using 2D arrays:

1. Determine array dimensions: Based on the problem, determine the number of rows and columns. The array size should be slightly larger than the maximum range given in the problem
2. Initialize the array: Choose an appropriate initialization method (use = {} for all zeros, use fill_n or memset for other values)
3. Read the data: Use nested loops to read elements of the 2D array
4. Process the data: Traverse, search, compute, etc. as required by the problem
5. Output the result: Use nested loops to output the result matrix

Standard pattern for traversing a 2D array:

1// Read an n-row, m-column 2D array
2for (int i = 0; i < n; ++i) {
3    for (int j = 0; j < m; ++j) {
4        cin >> arr[i][j];
5    }
6}
7
8// Output an n-row, m-column 2D array
9for (int i = 0; i < n; ++i) {
10    for (int j = 0; j < m; ++j) {
11        cout << arr[i][j];
12        if (j + 1 < m) cout << " ";  // separate elements in each row with spaces
13    }
14    cout << endl;
15}

✨ Common Mistakes with Multi-Dimensional Arrays

1. Array index out of bounds: For a 2D array arr[n][m], the valid index ranges are 0~n-1 and 0~m-1. Accessing arr[n][0] or arr[0][m] is out-of-bounds behavior
2. Confusing rows and columns: It is easy to mix up the number of rows and columns when working with matrices. Use meaningful variable names like rows and cols
3. Forgetting to specify column size in function parameters: When passing a 2D array as a function parameter, the second dimension must be explicitly specified, e.g., void f(int arr[][100], int n, int m)
4. Using memset to initialize to arbitrary values: memset assigns values byte by byte. It can only reliably initialize to 0, -1, 0x3f, 0x7f, and other special values. It cannot be used to initialize to 1 or other arbitrary integers (memset(arr, 1, sizeof(arr)) will not set each element to 1)
5. Defining large arrays inside the main function: Large 2D arrays (e.g., int arr[1000][1000]) should be defined outside the main function as global variables, otherwise stack overflow will occur

✨ Passing Multi-Dimensional Arrays to Functions

When passing multi-dimensional arrays to functions, all dimensions except the first must be explicitly specified in the function parameters. Note that the sizes here should match the full array dimensions.

1#include <iostream>
2using namespace std;
3
4// Function to print a 2D array
5void print2DArray(int arr[][3], int rows, int colums) {
6    for (int i = 0; i < rows; ++i) {
7        for (int j = 0; j < colums; ++j) {
8            cout << arr[i][j] << " ";
9        }
10        cout << endl;
11    }
12}
13
14int main() {
15    int arr[2][3] = {
16        {1, 2, 3},
17        {4, 5, 6}
18    };
19
20    print2DArray(arr, 2, 3);
21    return 0;
22}

1#include <iostream>
2using namespace std;
3
4// Function to print a 3D array
5void print3DArray(int arr[][3][4], int size1, int size2, int size3) {
6    for (int i = 0; i < size1; ++i) {
7        for (int j = 0; j < size2; ++j) {
8            for (int k = 0; k < size3; ++k) {
9                cout << arr[i][j][k] << " ";
10            }
11            cout << endl;
12        }
13        cout << endl;
14    }
15}
16
17int main() {
18    int arr[2][3][4] = {
19        {
20            {1, 2, 3, 4},
21            {5, 6, 7, 8},
22            {9, 10, 11, 12}
23        },
24        {
25            {13, 14, 15, 16},
26            {17, 18, 19, 20},
27            {21, 22, 23, 24}
28        }
29    };
30
31    print3DArray(arr, 2, 3, 4);
32    return 0;
33}

III. Homework

Knowledge Quiz

• Multi-Dimensional Arrays - Quiz

Programming Exercises

1. Matrix Transpose: L2204
2. Snake Number Filling: L2205