求实现MxN网格的连续对角线搜索算法（无跳转遍历）

核心逻辑 #

这种遍历的核心是模拟方向反弹的连续移动，无需拆分计算每条对角线，通过碰到网格边界时切换移动方向，保持路径的连续性。具体规则：

• 初始从网格左上角(0,0)出发，初始移动方向为右下（行+1，列+1）
• 碰到边界时切换方向：
  • 触碰到顶部/底部边界时，反转行方向（向下→向上，向上→向下）
  • 触碰到左/右边界时，反转列方向（向右→向左，向左→向右）
• 每一步按当前方向移动一个单元格，直到遍历完所有M*N个单元格

Java 实现示例 #

public class ContinuousDiagonalTraversal {
    public static void traverse(int[][] grid) {
        if (grid == null || grid.length == 0) return;
        
        int rows = grid.length;
        int cols = grid[0].length;
        int totalCells = rows * cols;
        
        int currRow = 0, currCol = 0;
        int dx = 1, dy = 1; // dx: 行方向增量，dy: 列方向增量

        for (int i = 0; i < totalCells; i++) {
            // 输出当前单元格值（实际场景可替换为业务逻辑）
            System.out.print(grid[currRow][currCol] + " ");

            // 计算下一个位置
            int nextRow = currRow + dx;
            int nextCol = currCol + dy;

            // 边界判断与方向调整
            boolean rowOutOfBounds = nextRow < 0 || nextRow >= rows;
            boolean colOutOfBounds = nextCol < 0 || nextCol >= cols;

            if (rowOutOfBounds) {
                dx = -dx; // 反转行方向
                nextRow = currRow + dx; // 重新计算合法行位置
            }
            if (colOutOfBounds) {
                dy = -dy; // 反转列方向
                nextCol = currCol + dy; // 重新计算合法列位置
            }

            // 更新当前位置
            currRow = nextRow;
            currCol = nextCol;
        }
    }

    public static void main(String[] args) {
        // 测试用3x3网格
        int[][] testGrid = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        traverse(testGrid);
        // 输出：1 2 5 3 6 9 8 7 4
    }
}

转换为MIPS汇编要点 #

1. 寄存器分配：
   • 用s0存储网格基地址，s1存总行数rows，s2存总列数cols
   • t0存当前行currRow，t1存当前列currCol
   • t2存行增量dx，t3存列增量dy
   • t4存总单元格数totalCells，t5存循环计数器
2. 内存访问：
   • 单元格地址计算：base + currRow * cols * 4 + currCol * 4（int类型占4字节）
3. 边界判断逻辑：
   • 比较nextRow与0、rows，nextCol与0、cols，越界则反转对应方向寄存器的值（取负）
4. 循环控制：
   • 从0循环到totalCells-1，每次循环更新当前位置并执行业务逻辑

内容的提问来源于stack exchange，提问作者user22597817