算法题解：蛇形矩阵

冷不防 2023-01-07 10:29 227阅读 0赞

**题目描述**

> 输入两个整数n和m，输出一个n行m列的矩阵，将数字 1 到 n\*m 按照回字蛇形填充至矩阵中。

**输入格式**

> 输入共一行，包含两个整数n和m。

**输出格式**

> 输出满足要求的矩阵。  
> 矩阵占n行，每行包含m个空格隔开的整数。

**数据范围**

> 1≤n,m≤100

**输入样例：**

> 3 3

**输出样例：**

> 1 2 3  
> 8 9 4  
> 7 6 5

**思路**：

1.  图形如下  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz_size_16_color_FFFFFF_t_70]
2.  一开始是从 （0 ，0）点出发，按照  
    右（偏移量为（0 ，1）：x不变，y加一）  
    → 下（偏移量为（1 ，0）：x加一，y不变）  
    → 左（偏移量为（0 ，-1）：x不变，y减一）  
    → 上（偏移量为（-1 ，0）：x减一，y不变）  
    …依次循环进行（顺时针走）  
    只有两种情况下，方向才会发生改变，分别是走到尽头或者说格子已被占用两种情况，我们可以定义右下左上四个方向分别用 0 1 2 3表示 也就是说四次一循环（除以4 取余）

**java题解代码：**

import java.util.Scanner;
    public class Main{ 
        public static void main(String[] args){ 
            // (0 ,1) (1 ,0) (0 , -1) (-1 , 0)
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int m = in.nextInt();
            int[][] arr = new int[n][m];
            // x,y偏移量 dx[0]--dy[0] dx[1]--dy[1] .....
            int[] dx = { 0, 1 , 0 , -1};
            int[] dy = { 1, 0 , -1 , 0};
            
            // 方向 0 1 2 3 右下左上
            int d = 0;
            // 起始坐标
            int x = 0;
            int y = 0;
            for (int i = 1 ; i <= n * m ; i++) { 
                // 走到下一个点的坐标
                int nx = x + dx[d];
                int ny = y + dy[d];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || arr[nx][ny] != 0) {  
                    d = (d + 1) % 4;
                    nx = x + dx[d];
                    ny = y + dy[d];
                }
                arr[x][y] = i;
                x = nx;
                y = ny;
            }
            
            for(int i = 0 ; i < n ; i++) { 
                for(int j = 0 ; j < m ;j++){ 
                    System.out.print(arr[i][j] + " ");
                }
                System.out.println();
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTIyMTEz_size_16_color_FFFFFF_t_70]: /images/20221119/3561df7d5f094c979edea79b5964dc02.png