解题思路

• 算法：对给定图像做二维仿射变换。仿射模型为 $x' = a x + b y + t_x,\quad y' = c x + d y + t_y$。 为避免“空洞”，采用逆映射 + 最近邻插值：对每个输出像素 $(x',y')$，先减去平移，再乘线性部分的逆矩阵，得到源坐标 $(x,y)$。若 $(x,y)$ 在原图范围内，则取最近邻像素；否则置 0。

• 核心实现：

  1. 从矩阵 $M=\begin{bmatrix}a&b&t_x\\c&d&t_y\end{bmatrix}$ 取出 $a,b,c,d,t_x,t_y$。
  2. 计算线性部分的逆:
  3. 枚举输出图像尺寸 $H\times W$ 的每个像素 $(x',y')$，

  

  取 $(\text{round}(x),\text{round}(y))$ 作为最近邻位置，越界则填 0。

• 坐标约定：x 为列、y 为行，左上角为 $(0,0)$。

• 输入输出： 第一行给出行数：a m o_lines。接着 a 行是图像 A；随后 m 行是 2×3 的变换矩阵 M；最后一行是输出尺寸 H W。 输出按行优先展平成一行空格分隔的数列。

复杂度分析

• 时间复杂度：枚举全部输出像素，$O(H \times W)$。
• 空间复杂度：保存输出图像，$O(H \times W)$（除输入外）。

代码实现

Python

# 题面功能封装在函数里；主函数做输入输出（ACM 风格）

from typing import List
import sys
import math

def affine_transform(A: List[List[int]], M: List[List[float]], H: int, W: int) -> List[List[int]]:
    # 解析仿射参数
    a, b, tx = M[0]
    c, d, ty = M[1]
    # 线性部分行列式
    det = a * d - b * c
    hA, wA = len(A), len(A[0]) if A else 0
    # 输出初始化为 0
    O = [[0 for _ in range(W)] for _ in range(H)]
    if abs(det) < 1e-12 or hA == 0 or wA == 0:
        return O

    # 预计算逆矩阵
    inv00 =  d / det
    inv01 = -b / det
    inv10 = -c / det
    inv11 =  a / det

    for y2 in range(H):          # y'
        for x2 in range(W):      # x'
            # 去掉平移再乘逆矩阵 -> 源坐标 (x, y)
            dx = x2 - tx
            dy = y2 - ty
            x = inv00 * dx + inv01 * dy
            y = inv10 * dx + inv11 * dy
            xi = int(round(x))
            yi = int(round(y))
            if 0 <= yi < hA and 0 <= xi < wA:
                O[y2][x2] = A[yi][xi]
    return O

def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    a = int(next(it)); m = int(next(it)); _ = int(next(it))  # O 占 1 行
    A = []
if __name__ == "__main__":
    import sys

    lines = sys.stdin.read().strip().splitlines()
    if not lines:
        sys.exit(0)
    a, m, _ = map(int, lines[0].split())
    idx = 1
    A = [list(map(int, lines[idx+i].split())) for i in range(a)]
    idx += a
    M = [list(map(float, lines[idx].split())), list(map(float, lines[idx+1].split()))]
    idx += m
    H, W = map(int, lines[idx].split())

    O = affine_transform(A, M, H, W)
    # 按行优先展平输出
    out = []
    for r in O:
        out.extend(map(str, r))
    print(" ".join(out))

Java

// 类名固定为 Main；主方法处理输入输出，功能写在外部静态函数里
import java.io.*;
import java.util.*;

public class Main {

    // 仿射变换，最近邻
    static int[][] affineTransform(int[][] A, double[][] M, int H, int W) {
        int hA = A.length;
        int wA = hA > 0 ? A[0].length : 0;
        int[][] O = new int[H][W];
        double a = M[0][0], b = M[0][1], tx = M[0][2];
        double c = M[1][0], d = M[1][1], ty = M[1][2];
        double det = a * d - b * c;
        if (Math.abs(det) < 1e-12 || hA == 0 || wA == 0) return O;

        // 线性部分逆矩阵
        double inv00 =  d / det, inv01 = -b / det;
        double inv10 = -c / det, inv11 =  a / det;

        for (int y2 = 0; y2 < H; y2++) {
            for (int x2 = 0; x2 < W; x2++) {
                double dx = x2 - tx;
                double dy = y2 - ty;
                double x = inv00 * dx + inv01 * dy;
                double y = inv10 * dx + inv11 * dy;
                int xi = (int)Math.round(x);
                int yi = (int)Math.round(y);
                if (0 <= yi && yi < hA && 0 <= xi && xi < wA) {
                    O[y2][x2] = A[yi][xi];
                } // 越界保持 0
            }
        }
        return O;
    }

    public static void main(String[] args) throws Exception {
        // 读取整段文本后逐行解析，避免 Scanner 过慢
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<String> lines = new ArrayList<>();
        String s;
        while ((s = br.readLine()) != null && s.length() > 0) lines.add(s);
        if (lines.isEmpty()) return;

        String[] t0 = lines.get(0).trim().split("\\s+");
        int a = Integer.parseInt(t0[0]);
        int m = Integer.parseInt(t0[1]); // 题目中 m=2
        // o_lines = Integer.parseInt(t0[2]); // 未用

        int idx = 1;
        int[][] A = new int[a][];
        for (int i = 0; i < a; i++) {
            String[] ts = lines.get(idx++).trim().split("\\s+");
            A[i] = new int[ts.length];
            for (int j = 0; j < ts.length; j++) A[i][j] = Integer.parseInt(ts[j]);
        }
        double[][] M = new double[2][3];
        for (int i = 0; i < 2; i++) {
            String[] ts = lines.get(idx++).trim().split("\\s+");
            for (int j = 0; j < 3; j++) M[i][j] = Double.parseDouble(ts[j]);
        }
        String[] ts = lines.get(idx).trim().split("\\s+");
        int H = Integer.parseInt(ts[0]);
        int W = Integer.parseInt(ts[1]);

        int[][] O = affineTransform(A, M, H, W);

        // 展平输出
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (out.length() > 0) out.append(' ');
                out.append(O[i][j]);
            }
        }
        System.out.println(out.toString());
    }
}

C++

// 主函数读入，功能放在独立函数；ACM 风格
#include <bits/stdc++.h>
using namespace std;

// 仿射变换：逆映射 + 最近邻
vector<vector<int>> affine_transform(const vector<vector<int>>& A,
                                     const array<array<double,3>,2>& M,
                                     int H, int W) {
    int hA = (int)A.size();
    int wA = hA ? (int)A[0].size() : 0;
    vector<vector<int>> O(H, vector<int>(W, 0));

    double a = M[0][0], b = M[0][1], tx = M[0][2];
    double c = M[1][0], d = M[1][1], ty = M[1][2];
    double det = a * d - b * c;
    if (fabs(det) < 1e-12 || hA == 0 || wA == 0) return O;

    // 线性部分逆矩阵
    double inv00 =  d / det, inv01 = -b / det;
    double inv10 = -c / det, inv11 =  a / det;

    for (int y2 = 0; y2 < H; ++y2) {
        for (int x2 = 0; x2 < W; ++x2) {
            double dx = x2 - tx;
            double dy = y2 - ty;
            double x = inv00 * dx + inv01 * dy;
            double y = inv10 * dx + inv11 * dy;
            int xi = (int)llround(x); // 最近邻
            int yi = (int)llround(y);
            if (0 <= yi && yi < hA && 0 <= xi && xi < wA) {
                O[y2][x2] = A[yi][xi];
            }
        }
    }
    return O;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, m, o;
    if (!(cin >> a >> m >> o)) return 0;

    // 读入图像 A（a 行）
    vector<vector<int>> A(a);
    cin.clear();
    cin.seekg(0, ios::beg);
    // 读整段
    vector<string> lines;
    string s;
    while (getline(cin, s)) if(!s.empty()) lines.push_back(s);
    if (lines.empty()) return 0;
    {
        stringstream ss(lines[0]);
        ss >> a >> m >> o;
    }
    int idx = 1;
    A.clear(); A.reserve(a);
    for (int i = 0; i < a; ++i) {
        stringstream ss(lines[idx++]);
        vector<int> row; int v;
        while (ss >> v) row.push_back(v);
        A.push_back(row);
    }
    array<array<double,3>,2> M;
    for (int i = 0; i < 2; ++i) {
        stringstream ss(lines[idx++]);
        for (int j = 0; j < 3; ++j) ss >> M[i][j];
    }
    int H, W;
    {
        stringstream ss(lines[idx]);
        ss >> H >> W;
    }

    auto O = affine_transform(A, M, H, W);

    // 展平输出
    bool first = true;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (!first) cout << ' ';
            first = false;
            cout << O[i][j];
        }
    }
    cout << '\n';
    return 0;
}

题目内容

人脸关键点对齐是人脸识别算法过程中非常重要的一步，其方法是基于检测人脸关键点及模板人脸关键点获得变换矩阵 $M$ ，使得最小二乘意义下把原图的关键点贴到模板关键点位置，其基本原理是对图像得仿射变换。现在你将实现一个图像的仿射变换函数，该函数接收一个二维图像矩阵 $A$ 、一个变换矩阵 $M$ 和输出图像的尺寸 $0$ ，返回变换后的图像。

变换公式为，其中 $x,y$ 为原坐标， $x',y'$ 为变换后的坐标， $a,b,c,d$ 是线性变换部分的系数， $t_x,t_y$ 是平移向量: $x'=a×x+b×y+t_x$

$y'=c×x+d×y+t_y$

如果变换后的坐标超出原图像范围，则不赋值(保留为 $0$ )。

输入描述

输入图像 $A$ :一个二维列表，表示输入图像，每个元素是一个像素值。

交换矩阵 $M$ :一个二维列表，格式如下:

$[[a, b, t_ x], [c,d,t_y]]$

输出图像的尺寸 $height, width$

输入第一行分别为 $A、M$ 列表的长度 $a,m$ 以及输出列表 $O$ 所占用的行，接下来的 $a$ 行为输入图像 $A$ ，然后 $m$ 行是输入变换矩阵，最后一行是输出图像的大小

输出描述

返回一个二维列表，表示变换后的图像

样例1

输入

3 2 1
10 20 30
40 50 60
70 80 90
0 1 0
-1 0 2
3 3

输出

30 60 90 20 50 80 10 40 70

说明

第一行 $3$ $2$ $1$ 表示:

从第二行起接下来的三行是图像 $A$ 的输入，然后下面两行是变换矩阵的输入，最后一行是输出图像的高度及宽度

输出图像矩阵为 $[[30,60,90],[20,50,80],[10,40,70]$ ,

展开后最终的输出为 $30$ $60$ $90$ $20$ $50$ $80$ $10$ $40$ $70$

样例2

输入

3 2 1
10 20 30
40 50 60
70 80 90
-1 0 2
0 1 0
3 4

输出

30 20 10 0 60 50 40 0 90 80 70 0

提示

1.如果变换矩阵的线性部分 $(a,b,c,d)$ 不可逆，则返回一个全 $0$ 的图像