/*
Time limit: 5000ms
Memory limit: 256mb
---------------------Copy the following code, complete it and submit---------------------
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Matrix ADT
struct Matrix {
int *data;
int rows;
int cols;
};
// Function prototypes
// create a matrix with given dimensions with all elements initialized to 0
struct Matrix create_matrix(int rows, int cols);
// free the memory allocated for a matrix
void free_matrix(struct Matrix m);
// set the element at given position
void set_element(struct Matrix m, int row, int col, int value);
// get the element at given position
int get_element(struct Matrix m, int row, int col);
// multiply two matrices
struct Matrix matrix_multiply(struct Matrix A, struct Matrix B);
/**
* @brief Create a matrix with given dimensions with all elements initialized to 0
* @param rows number of rows
* @param cols number of columns
* @return a Matrix struct
*/
struct Matrix create_matrix(int rows, int cols) {
struct Matrix m;
m.rows = rows;
m.cols = cols;
m.data = (int *)malloc(rows * cols * sizeof(int));
memset(m.data, 0, rows * cols * sizeof(int));
return m;
}
/**
* @brief Free the memory allocated for a matrix
* @param m a Matrix struct
*/
void free_matrix(struct Matrix m) {
free(m.data);
}
/**
* @brief Set the element at given position
* @param m a Matrix struct
* @param row row index
* @param col column index
* @param value the value to set
*/
void set_element(struct Matrix m, int row, int col, int value) {
m.data[row * m.cols + col] = value;
}
/**
* @brief Get the element at given position
* @param m a Matrix struct
* @param row row index
* @param col column index
* @return the value at the given position
*/
int get_element(struct Matrix m, int row, int col) {
return m.data[row * m.cols + col];
}
/**
* @brief Multiply two matrices
* @param A a Matrix struct (n by k)
* @param B a Matrix struct (k by m)
* @return the result matrix C = A * B (n by m)
*/
struct Matrix matrix_multiply(struct Matrix A, struct Matrix B) {
// Check if the matrices can be multiplied
if (A.cols != B.rows) { abort(); }
// Hint: C[i][j] = sum of A[i][l] * B[l][j] for all l from 0 to k-1
// WRITE YOUR CODE HERE
}
// DO NOT MODIFY THE CODE BELOW
int main(void) {
int n, k, m;
scanf("%d %d %d", &n, &k, &m);
// Read matrix A (n by k)
struct Matrix A = create_matrix(n, k);
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
int value;
scanf("%d", &value);
set_element(A, i, j, value);
}
}
// Read matrix B (k by m)
struct Matrix B = create_matrix(k, m);
for (int i = 0; i < k; i++) {
for (int j = 0; j < m; j++) {
int value;
scanf("%d", &value);
set_element(B, i, j, value);
}
}
// Compute C = A * B
struct Matrix C = matrix_multiply(A, B);
// Output matrix C
for (int i = 0; i < C.rows; i++) {
for (int j = 0; j < C.cols; j++) {
if (j > 0) printf(" ");
printf("%d", get_element(C, i, j));
}
printf("\n");
}
free_matrix(A);
free_matrix(B);
free_matrix(C);
return 0;
}
---------------------------------------End of Code---------------------------------------
## Matrix Multiplication
In this problem, you need to implement a Matrix ADT that supports matrix multiplication. Given two matrices $\mathbf{A}$ and $\mathbf{B}$, compute their product $\mathbf{C} = \mathbf{A} \times \mathbf{B}$.
Let $\mathbf{A}$ be an $n \times k$ matrix and $\mathbf{B}$ be a $k \times m$ matrix. Their product $\mathbf{C} = \mathbf{A} \times \mathbf{B}$ is an $n \times m$ matrix where:
$$c_{i,j} = \sum_{\ell=1}^{k} a_{i,\ell} \cdot b_{\ell,j}$$
In other words, the element at position $(i, j)$ in the result matrix is the dot product of the $i$-th row of $\mathbf{A}$ and the $j$-th column of $\mathbf{B}$.
The Matrix ADT should support the following operations:
- `create_matrix(int rows, int cols)`: Create a new matrix with given dimensions.
- `free_matrix(Matrix m)`: Free the memory used by the matrix.
- `set_element(Matrix m, int row, int col, int value)`: Set the element at position $(row, col)$ to `value`.
- `get_element(Matrix m, int row, int col)`: Get the element at position $(row, col)$.
- `matrix_multiply(Matrix A, Matrix B)`: Compute the product of matrices $\mathbf{A}$ and $\mathbf{B}$.
Note that some operations have been implemented in the given code template. You need to implement the `matrix_multiply` function.
### Input
- First line contains three integers $n$, $k$, and $m$ ($1 \leq n, k, m \leq 100$):
- $n$: number of rows in matrix $\mathbf{A}$
- $k$: number of columns in matrix $\mathbf{A}$ (also number of rows in matrix $\mathbf{B}$)
- $m$: number of columns in matrix $\mathbf{B}$
- Next $n$ lines: each line contains $k$ integers representing a row of matrix $\mathbf{A}$. All values are in range $[-100, 100]$.
- Next $k$ lines: each line contains $m$ integers representing a row of matrix $\mathbf{B}$. All values are in range $[-100, 100]$.
### Output
Output $n$ lines, each containing $m$ integers separated by spaces — the result matrix $\mathbf{C} = \mathbf{A} \times \mathbf{B}$.
### Example
**Input**
```
2 3 2
1 2 3
4 5 6
1 0
0 1
1 1
```
**Output**
```
4 5
10 11
```
**Explanation**
Matrix $\mathbf{A}$ is:
$$\mathbf{A} = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}$$
Matrix $\mathbf{B}$ is:
$$\mathbf{B} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{bmatrix}$$
The product $\mathbf{C} = \mathbf{A} \times \mathbf{B}$ is:
$$\mathbf{C} = \begin{bmatrix} 1 \cdot 1 + 2 \cdot 0 + 3 \cdot 1 & 1 \cdot 0 + 2 \cdot 1 + 3 \cdot 1 \\ 4 \cdot 1 + 5 \cdot 0 + 6 \cdot 1 & 4 \cdot 0 + 5 \cdot 1 + 6 \cdot 1 \end{bmatrix} = \begin{bmatrix} 4 & 5 \\ 10 & 11 \end{bmatrix}$$