矩阵运算¶

矩阵加法¶

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        c[i][j] = a[i][j] + b[i][j];

矩阵乘法¶

int a[N][M], b[M][K], c[N][K], n, m, k; // [n ,m] * [m, k]

int main() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++)
            for (int p = 1; p <= m; p++)
                c[i][j] += a[i][p] * b[p][k];

    ...
}

对角线问题¶

左上到右下，这条对角线上的点

特征：行等于列，i == j

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        if (i == j) cout << a[i][j] << ' ';

左下到右上，这条对角线上的点

特征：行 + 列 = n + 1

for (int i = n; i >= 1; i--)
    for (int j = 1; j <= n; j++)
        if (i + j == n + 1) cout << a[i][j] << ' ';

同行、同列、同斜线问题¶

同行，就是行号一样。钉住行号，枚举列

for (int j = 1; j <= m; j++) cout << a[x][j] << ' ';

同列，就是列号一样。钉住列号，枚举行

for (int i = 1; i <= n; i++) cout << a[i][y] << ' ';

同斜线，和 (x, y) 同在一条斜线上，

从左上到右下遍历

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        if (x + y == i + j) cout << a[i][j] << ' ';

同斜线，和 (x, y) 同在一条斜线上，

从左下到右上遍历

for (int i = n; i >= 1; i--)
    for (int j = 1; j <= n; j++)
        if (y - x == j - i) cout << a[i][j] << ' ';

矩阵转置¶

转置是将原矩阵的行变成列，列变成行。

从[遍历行]，转向到[遍历列]，改变[遍历顺序]，直接输出

cin >> n >> m;

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        cin >> a[i][j];

for (int j = 1; j <= m; j++) {
    for (int i = 1; i <= n; i++) cout << a[i][j] << ' ';
    cout << endl;
}

枚举移动前的元素，考虑将这些元素移动到什么位置

cin >> n >> m;

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        cin >> a[i][j];

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        b[j][i] = a[i][j];

枚举移动后的元素，寻找这个位置的元素从哪过来的

for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
        b[i][j] = a[j][i];

向右旋转90°(难点)¶

n * n 的矩阵，向右旋转 90°

// 盯住 a[i][j] 这个位置，看旋转到哪去
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        b[j][n + 1 - j] = a[i][j];

// 盯住 b[i][j] 这个位置，看从哪旋转过来的
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        b[i][j] = a[n + 1 - j][i];

同理，向左旋转 90°，也是类似的写法。

矩阵的填充(难点)¶

2045：【例5.13】蛇形填数

#include <bits/stdc++.h>

using namespace std;

int a[25][25], n;
int idx;

int main()
{
    cin >> n;

    int i = 1, j = n;
    while (idx < n * n){
        while (i <= n && !a[i][j]) a[i++][j] = ++idx;
        i--, j--;

        while (j >= 1 && !a[i][j]) a[i][j--] = ++idx;
        j++, i--;

        while (i >= 1 && !a[i][j]) a[i--][j] = ++idx;
        i++, j++;

        while (j <= n && !a[i][j]) a[i][j++] = ++idx;
        i++, j--;
    }

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++) cout << a[i][j] << ' ';
        puts("");
    }

    return 0;
}

// 第二种写法
#include<bits/stdc++.h>

using namespace std;

const int N = 25;

int a[N][N], n;
int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};  // delta
int idx = 1;

int main(){
    cin >> n;

    int i = 1, j = n;
    while (idx < n * n){
        for (int k = 0; k < 4; k++){
            while (true){
                a[i][j] = idx++;
                i += dx[k], j += dy[k];
                if (i > n || i < 1 || j > n || j < 1 || a[i][j]){
                    i -= dx[k], j -= dy[k], idx--;
                    break;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++) cout << a[i][j] << ' ';
        puts("");
    }

    return 0;
}

3368：练63.2 斜行方阵

#include <bits/stdc++.h>

using namespace std;

const int N = 25;

int a[N][N], n;

bool check(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= n;
}

int main() {
    cin >> n;

    int x = 1, y = n, idx = 1;
    int px = 1, py = n;
    while (idx <= n * n) {
        x = px, y = py;
        if (px == 1) py--;
        else px ++;

        if (py < 1) {
            py = 1;
            px++;;
        }

        while (check(x, y)) {
            a[x++][y++] = idx++;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) printf("%4d", a[i][j]);
        puts("");
    }

    return 0;
}

22:神奇的幻方

#include <iostream>

using namespace std;

int a[50][50], n;

int main() {
    cin >> n;

    int x = 1, y = n, idx = 1;
    n = 2 * n - 1;
    while (idx <= n * n) {
        a[x][y] = idx++;

        if (x == 1) {
            if (y == n) x++;
            else x = n, y++;
        }
        else if (y == n) y = 1, x--;
        else if (a[x - 1][y + 1]) x++;
        else x--, y++;
    }

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++) cout << a[i][j] << ' ';
        puts("");
    }

    return 0;
}