AcWing 756. 蛇形矩阵

系统管理员 2023-01-07 14:27 176阅读 0赞

**上一篇博客：[AcWing 1113. 红与黑（BFS、DFS）][AcWing 1113. _BFS_DFS]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[AcWing 756. 蛇形矩阵][AcWing 756.]

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  输入格式
     *  输出格式
     *  数据范围
     *  输入样例
     *  输出样例
 *  题解
 *   *  解题思路
     *   *  while循环思路
         *  解题代码
         *  for循环思路
         *  解题代码

# 题目信息 #

## 题目描述 ##

输入两个整数 **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**

# 题解 #

## 解题思路 ##

本题主要是考察了数组，我们可以使用两种方法解决本题目。第一种方法是使用 `while循环`，第二种方法是使用 `for循环`。

### while循环思路 ###

首先设置初始坐标为 `(0, 0)`，然后将结果二维数组 `q[N][N]` 的第一个元素设置为 `1`，计数器 `cnt` 的初始值为 `1`。使用while循环来进行填数，只要 `cnt < n * m` 就进行填数。使用四条 **while** 循环来依次填4个方向的数字，先判断下一个要填的位置是否出界，如果没有出界在判断该位置的数字是否已经填过数字了，如果没有填过则将 `++cnt` 赋值给下一个数组元素。直到填完整个数组。

### 解题代码 ###

#include<iostream>
    #include<algorithm>
    using namespace std;
    
    const int N = 110;
    int q[N][N];
    
    int main() { 
        int n, m;
        cin >> n >> m;
        int cnt = 1;
        int x = 0, y = 0;
        q[x][y] = 1;
        while (cnt < n * m) {   
            while (y + 1 < m && !q[x][y + 1]) q[x][++y] = ++cnt;
            while (x + 1 < n && !q[x + 1][y]) q[++x][y] = ++cnt;
            while (y > 0 && !q[x][y - 1]) q[x][--y] = ++cnt;
            while (x > 0 && !q[x - 1][y]) q[--x][y] = ++cnt;
        }
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < m; j++) { 
                cout << q[i][j] << " ";
            }
            cout << endl;
        }
        return 0;
    }

### for循环思路 ###

一直向一个方向填数，如果 `下一个位置出界` 或者 `已经被填过数了`，那么就改变方向继续进行填数。

### 解题代码 ###

#include<iostream>
    using namespace std;
    
    const int N = 110;
    int m, n;
    int q[N][N];
    
    bool inmap(int x, int y) { 
        return x >= 0 && x < n && y >= 0 && y < m;
    }
    
    int main() { 
        cin >> n >> m;
        int dx[] = { -1, 0, 1, 0}, dy[] = { 0, 1, 0, -1};
        int x = 0, y = 0, d = 1;
        for (int i = 1; i <= n * m; i++) { 
            q[x][y] = i;
            int x1 = x + dx[d], y1 = y + dy[d];
            // 如果出界或者下一个已经被填过了，那么就改变方向并更新坐标
            if (!inmap(x1, y1) || q[x1][y1]) { 
                d = (d + 1) % 4;
                x1 = x + dx[d];
                y1 = y + dy[d];
            }
            x = x1, y = y1;
        }
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < m; j++) { 
                cout << q[i][j] << ' ';
            }
            cout << endl;    
        }
        return 0;
    }

--------------------

> 未完待续，持续更新中……  
> ![在这里插入图片描述][20210118111123356.png]

[AcWing 1113. _BFS_DFS]: https://ac-fun.blog.csdn.net/article/details/112635729
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[AcWing 756.]: https://www.acwing.com/problem/content/758/
[20210118111123356.png]: /images/20221119/66e25a76b3d442ee93afd8fed3d98240.png