来源于@的课程
深度优先搜索-0-简介
一、搜索算法的原理
- 搜索算法的原理就是枚举。利用计算机的高性能，给出人类制定好的规则，枚举出所有可行的情况，找到可行解或者最优解。
- 比较常见的搜索算法是 深度优先搜索（又叫深度优先遍历） 和 广度优先搜索（又叫广度优先遍历 或者 宽度优先遍历）。各种图论的算法基本都是依靠这两者进行展开的。
- 深度优先搜索一般用来求可行解，利用[剪枝]进行优化，在树形结构的图上用处较多；而广度优先搜索一般用来求最优解，配合哈希表进行状态空间的标记，从而避免重复状态的计算；
二、深度优先搜索定义
1. 什么是DFS？
深度优先搜索（Depth First Search，简称DFS大法师）是一种用于遍历或搜索树/图的算法。它的特点是：
- 沿着一条路径一直走到底
- 当无法继续前进时才回溯
- 确保访问到所有的节点
想象你在走迷宫：
- 每到一个分岔路口，你总是先选择一条路一直走
- 走到死胡同时，才返回到最近的分岔路口，选择另一条路
- 这就是DFS的基本思想
dfs算法具体算法描述为：
选择一个起始点 作为 当前结点，执行如下操作：
a. 访问 当前结点，并且标记该结点已被访问，然后跳转到 b；
b. 如果存在一个和 当前结点 相邻并且尚未被访问的结点 ，则将 设为 当前结点，继续执行 a；
c. 如果不存在这样的 ，则进行回溯，回溯的过程就是回退 当前结点；
- 上述所说的 当前结点 需要用一个栈来维护，每次访问到的结点入栈，回溯的时候出栈。除了栈，另一种实现深度优先搜索的方式是递归，代码更加简单，相对好理解。
- 上述所说的 当前结点 需要用一个栈来维护，每次访问到的结点入栈，回溯的时候出栈。除了栈，另一种实现深度优先搜索的方式是递归，代码更加简单，相对好理解。
【例题1】给定一个 n 个结点的无向图，要求从 0 号结点出发遍历整个图，求输出整个过程的遍历序列。其中，遍历规则为：
1）如果和 当前结点 相邻的结点已经访问过，则不能再访问；
2）每次从和 当前结点 相邻的结点中寻找一个编号最小的没有访问的结点进行访问；
- 如图1所示，对上图以深度优先的方式进行遍历，起点是 0；
- <1> 第一步，当前结点为 0，标记已访问，然后从相邻结点中找到编号最小的且没有访问的结点 1；
- <2> 第二步，当前结点为 1，标记已访问，然后从相邻结点中找到编号最小的且没有访问的结点 3；
- <3> 第三步，当前结点为 3，标记已访问，没有尚未访问的相邻结点，执行回溯，回到结点 1；
- <4> 第四步，当前结点为 1，从相邻结点中找到编号最小的且没有访问的结点 4；
- <5> 第五步，当前结点为 4，标记已访问，然后从相邻结点中找到编号最小的且没有访问的结点 5；
- <6> 第六步，当前结点为 5，标记已访问，然后从相邻结点中找到编号最小的且没有访问的结点 2；
- <7> 第七步，当前结点为 2，标记已访问，然后从相邻结点中找到编号最小的且没有访问的结点 6；
- <8> 第八步，当前结点为 6，标记已访问，没有尚未访问的相邻结点，执行回溯，回到结点 2；
- <9> 第九步，按照 2 => 5 => 4 => 1 => 0 的顺序一路回溯，搜索结束；
- 如下图所示，红色实箭头表示搜索路径，蓝色虚箭头表示回溯路径。
- 图中，红色块表示往下搜索，蓝色块表示往上回溯，遍历序列为：
0 -> 1 -> 3 -> 4 -> 5 -> 2 -> 6
2. DFS的核心特征
- 递归性
- 问题可以分解为子问题
- 子问题的解决方式与原问题相同
- 有明确的终止条件
- 回溯性
- 当前路径不通时，返回上一步
- 尝试其他可能的选择
- 记录和恢复状态
- 完整性
- 保证访问所有可能的路径
- 不会重复访问节点
- 一定能找到解（如果存在）
三、深度优先搜索题型分类
1. 连通块问题
2. 路径搜索问题
3. 排列组合问题
4. 复杂约束问题
1 条评论
-
gf24240 LV 7 MOD @ 2026-2-4 14:34:30二维数组图形规律
一、二维数组的遍历规律
1、一维数组遍历
我们从一维数组的遍历拓展到二维数组的遍历
int n=10,k=0,a[10]; for(int i=0;i<n;i++){//顺序遍历填数 a[i]=k++; } for(int i=n-1;i>0;i--){//倒序遍历输出 cout<<a[i]<<" "; }2、二维数组遍历
由二维数组的定义可知，二维数组相当于一维数组里面嵌套了一个一维数组（如下图），所以二维数组的遍历相当于在一维数组的 ii 循环里面再嵌套一个 jj 循环。
(本文的讨论分析，均假设二维数组不包含第 00** 行，第 00 列，包含的情况，请大家自行分析)**
//不考虑第0行，第0列 //图1 外循环为行i，内循环为每列j #include <bits/stdc++.h> using namespace std; int main() { int a[10][10],n=4,m=4,k=0; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { a[i][j]= ++k;//遍历顺序 } } for(int i=1; i<=n; i++) {//输出 for(int j=1; j<=n; j++) { cout<<setw(3)<<a[i][j]; } cout<<endl; } return 0; }上述代码输出结果为：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16思考如下图形的遍历顺序：
//不考虑第0行，第0列 //以下代码仅修改图1代码的第7-11行 //图2 外循环i是倒序，内循环j也是倒序 for(int i=n;i>=1;i--){ for(int j=m;j>=1;j--){ a[i][j]= ++k; } } //图3 外循环j是顺序，内循环i也是顺序 for(int j=1;j<=m;j++){ for(int i=1;i<=n;i++){ a[i][j]= ++k; } } //图4 外循环j是倒序，内循环i是顺序 for(int j=1;j<=m;j++){ for(int i=1;i<=n;i++){ a[i][j]= ++k; } }3、二维数组遍历进阶
斜向顺序遍历1：
#include <bits/stdc++.h> using namespace std; int i,j,n,a[20][20] = {0},t=0; int main(){ cin>>n; for(i = 1;i<=n;i++){ for(j = 1;j <=i;j++){ a[j][i-j+1] = ++t;//观察第三行(1,3) (2,2) (3,1) i=3 j=1 2 3 } } //输出 for(i = 1;i <= n;i++){ for(j = 1;j <= n;j++){ cout<<setw(3)<<a[i][j]; } cout<<endl; } return 0; }上述代码输出结果为：
1 2 4 7 11 3 5 8 12 0 6 9 13 0 0 10 14 0 0 0 15 0 0 0 0斜向顺序遍历2：
#include <bits/stdc++.h> using namespace std; int i,j,n,m,a[20][20] = {0},t=0; int main(){ cin>>n; for(i = 1;i<=2*n-1;i++){//斜向的行数i if(i<=n)m=i; //左上角 else m=n-i%n; //右下角 for(j = 1;j <=m;j++){//斜向的列数j m=1,2...n...2,1; if(i<=n)a[j][i-j+1] = ++t;//填写左上角 else a[i%n+j][n-j+1]=++t; //填写右下角 } } //输出 for(i = 1;i <= n;i++){ for(j = 1;j <= n;j++){ cout<<setw(3)<<a[i][j]; } cout<<endl; } return 0; }上述代码输出结果为：
1 2 4 7 11 3 5 8 12 16 //i=6 j=1 2 3 4 (2,5) (3,4) (4,3) (5,2) 6 9 13 17 20 //i=7 j=1 2 3 (3,5) (4,4) (5,3) 10 14 18 21 23 15 19 22 24 25找出以下矩阵的规律，思考如何得到以下矩阵：
1 3 6 10 15 11 7 4 2 1 25 24 22 19 15 15 19 22 24 25 2 5 9 14 19 16 12 8 5 3 23 21 18 14 10 10 14 18 21 23 4 8 13 18 22 20 17 13 9 6 20 17 13 9 6 6 9 13 17 20 7 12 17 21 24 23 21 18 14 10 16 12 8 5 3 3 5 8 12 16 11 16 20 23 25 25 24 22 19 15 11 7 4 2 1 1 2 4 7 11斜向顺序遍历3：
for(i = 1;i<=n;i++){ for(j = 1;j <= n - i+1;j++){ a[i+j-1][j] = t;//左下角部分 a[j][i+j-1] = t;//右下角部分 t++; } }上述代码输出结果为：
1 6 10 13 15 6 2 7 11 14 10 7 3 8 12 13 11 8 4 9 15 14 12 9 5利用下文数组对称规则，可以简单修改第9和第10行代码即可得到各种对称翻转后的图形。
15 13 10 6 1 15 14 12 9 5 5 9 12 14 15 14 11 7 2 6 13 11 8 4 9 9 4 8 11 13 12 8 3 7 10 10 7 3 8 12 12 8 3 7 10 9 4 8 11 13 6 2 7 11 14 14 11 7 2 6 5 9 12 14 15 1 6 10 13 15 15 13 10 6 1【BCOI】 习题：
二、二维数组对角线规律
数组a[6][6]a[6][6]，n=5n=5，第 ii行，第jj 列为 a[i][j]a[i][j]，且先不考虑第00行，第00列的情况。
观察上图可知，二维数组a[i][j]a[i]**[j]左斜对角线上格子的（j−i)（j−i)的值都相等，右斜对角线上格子的(j+i)(j+i)**的值都相等。
下面我们分左斜和右斜两种情况讨论。
1、左斜对角线
每条对角线上的a[i][j]a[i][j]均具有 kk 值规律，即每条对角线上的格子的j−ij−i(或i−ji−j)的值均相等。
kk 值可以根据题意 ±d**±**d ，将上述k值序列，进行数位移位从而得到新的序列值（见上图）。
根据kk值规律，我们可以把二维数组分为上下两部分：
int k=j-i; if(k==0)为红色对角线上的格子 if(k<0)为左下角绿色部分格子 if(k>0)为右上角蓝色部分格子根据对角线规则，就可以很简单的得到符合对角线规则的二维矩阵：
左斜矩阵一：
#include <bits/stdc++.h> using namespace std; int main() { int a[6][6],n=5; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { a[i][j]=j-i;//k=j-i; } } for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { cout<<setw(3)<<a[i][j]; } cout<<endl; } return 0; }上述代码将a[i][j]a[i]**[j]**数组赋值为：
0 1 2 3 4 -1 0 1 2 3 -2 -1 0 1 2 -3 -2 -1 0 1 -4 -3 -2 -1 0左斜矩阵二：
int a[6][6],n=5; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ a[i][j]=n-(j-i);//k=n-(j-i); } }上述代码将a[i][j]a[i]**[j]**数组赋值为：
5 4 3 2 1 6 5 4 3 2 7 6 5 4 3 8 7 6 5 4 9 8 7 6 5左斜矩阵三：
int a[6][6],n=5; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ a[i][j]=n-(i-j);//k=n-(i-j); } }上述代码将a[i][j]a[i]**[j]**数组赋值为：
5 6 7 8 9 4 5 6 7 8 3 4 5 6 7 2 3 4 5 6 1 2 3 4 5左斜矩阵四：
如果取上述矩阵二的右上角和矩阵三的左下角部分，得到新的矩阵四：
for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(j-i>=0) a[i][j]=n-(j-i);//对角线右上角 else a[i][j]=n-(i-j);//对角线左下角 } }上述代码将a[i][j]a[i]**[j]**数组赋值为：
5 4 3 2 1 4 5 4 3 2 3 4 5 4 3 2 3 4 5 4 1 2 3 4 5上述矩阵四也可使用以下更加简洁的代码赋值得到：
for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { a[i][j]=n-abs(i-j); } }2、右斜对角线
每条对角线上的a[i][j]a[i][j]均具有 kk 值规律，即每条对角线上的格子的 i+ji+j 的值均相等。
kk 值可以根据题意 ±d**±**d ，将上述k值序列，进行数位移位从而得到新的序列值（见上图）。
同样根据 kk 值规律，我们可以把二维数组分为上下两部分：
int k=i+j-1; if(k==n)为红色对角线上的格子 if(k<n)为左上角橙色部分格子 if(k>n)为右下角紫色部分格子根据对角线规则，就可以很简单的得到符合对角线规则的二维矩阵：
右斜矩阵五：
#include <bits/stdc++.h> using namespace std; int main() { int a[6][6],n=5; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { a[i][j]=i+j-1;//k=i+j-1; } } for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { cout<<setw(3)<<a[i][j]; } cout<<endl; } return 0; }上述代码将a[i][j]a[i]**[j]**数组赋值为：
1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8 5 6 7 8 9右斜矩阵六：
int a[6][6],n=5; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ a[i][j]=2*n-(i+j-1); } }上述代码将a[i][j]a[i]**[j]**数组赋值为：
9 8 7 6 5 8 7 6 5 4 7 6 5 4 3 6 5 4 3 2 5 4 3 2 1右斜矩阵七：
如果取上述矩阵一的左上角和矩阵二的右下角部分，得到新的矩阵三：
for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(i+j-1<n) a[i][j]=i+j-1;//对角线左上角 else a[i][j]=2*n-(i+j-1);//对角线右下角 } }上述代码将a[i][j]a[i]**[j]**数组赋值为：
1 2 3 4 5 2 3 4 5 4 3 4 5 4 3 4 5 4 3 2 5 4 3 2 1包含第0行和第0列数组的对角线规则
参考例题：
三、数组对称规则
**数组对称规则非常实用，解题时注意观察图形规律，然后利用对称规则可以让问题简化很多，例如很多时候只需要考虑一半或者四分之一的部分答案，剩下部分直接利用对称原理赋值即可。**本章的方阵填数，大部分都可以用这个规则来优化。
1、一维数组对称规则
int a[10],n=5; for(int i=1;i<=n/2;i++){//循环一半 a[i]=a[n-i+1]=i;//头尾对称赋值 }上述代码将a[i]a[i]数组赋值为：
1 2 3 2 1可以利用一维数组对称规则，判定头尾是否相等，从而验证数列或者字符串为回文数：
char c[105]; bool flag=0; cin>>c+1;//表示字符串从c[1]开始存储，跳过c[0]位置； int n=strlen(c); for(int i=1;i<=n/2;i++){ if(c[i]!=c[n-i+1]){ flag=1;break; } } if(!flag)c是回文串; else c不是回文串根据上述对称规则可知：
n−i+1n−i+1：表示把 ii 倒序一下 n−j+1n−j+1：表示把 jj 倒序一下
上述规则在下面会经常用到。
2、二维数组对称规则
a) 关于 j=(n+1)/2j=(n+1)/2 左右对称
二维数组关于 kk 左右对称，则行 ii 不变，jj 方向成一维数组对称规则，即a[i][j]a[i][n−j+1]a[i][j]a[i][n−j+1]
#include <bits/stdc++.h> using namespace std; int main() { int a[6][6],n=5,cnt=0; for(int i=1; i<=n; i++) { for(int j=1; j<=(n+1)/2; j++) { a[i][j]=a[i][n-j+1]=++cnt; } } for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { cout<<setw(3)<<a[i][j]; } cout<<endl; } return 0; }上述代码将a[i][j]a[i]**[j]**数组赋值为：
1 2 3 2 1 4 5 6 5 4 7 8 9 8 7 10 11 12 11 10 13 14 15 14 13b) 关于 i=(n+1)/2i=(n+1)/2 上下对称
二维数组关于 kk 上下对称，则行 jj 不变，ii 方向成一维数组对称规则，即a[i][j]a[n−i+1][j]a[i][j]a[n−i+1][j]
int a[6][6],n=5,cnt=0; for(int i=1; i<=(n+1)/2; i++) { for(int j=1; j<=n; j++) { a[i][j]=a[n-i+1][j]=++cnt; } }上述代码将a[i][j]a[i]**[j]**数组赋值为：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 6 7 8 9 10 1 2 3 4 5c) 关于左斜对角线 j−i=0j−i=0 对称
二维数组关于 j−i=0j−i=0 斜对称的规则为， ii 和 jj 坐标互换即 a[i][j]=a[j][i]a[i][j]=a[j][i]
根据对角线对称规则，上面左斜矩阵四的代码还可以更简洁的写为：
int a[6][6],n=5,cnt=0; for(int i=1; i<=n; i++) { for(int j=i; j<=n; j++) { a[i][j]=a[j][i]=n-(j-i);//对角线上下对称，可以同时赋值 } } /* 上面代码也可以写为以下形式 int a[6][6],n=5,cnt=0; for(int i=1; i<=n; i++) { for(int j=1; j<=i; j++) { a[i][j]=a[j][i]=n-(i-j); } } */上述代码将a[i][j]a[i]**[j]**数组赋值为：
5 4 3 2 1 4 5 4 3 2 3 4 5 4 3 2 3 4 5 4 1 2 3 4 5d) 关于右斜对角线 j+i=n+1j+i=n+1 对称
二维数组关于 i+j=n+1i+j=n+1 斜对称的规则为，先分别把 (i,j)(i,j) 的 ii 和 jj 进行倒序对称成为 (n−i+1,n−j+1)(n−i+1,n−j+1)，然后互换横纵坐标，得到关于红色对角线对称的点 (n−j+1,n−i+1)(n−j+1,n−i+1) 即 a[i][j]=a[n−j+1][n−i+1]a[i][j]=a[n−j+1][n−i+1]
根据对角线对称规则，上面右斜矩阵七的代码还可以更简洁的写为：
for(int i=1; i<=n; i++) { for(int j=1; j<=n-i+1; j++) { a[i][j]=a[n-j+1][n-i+1]=i+j-1; } }上述代码将a[i][j]a[i]**[j]**数组赋值为：
1 2 3 4 5 2 3 4 5 4 3 4 5 4 3 4 5 4 3 2 5 4 3 2 1e) 关于中心点对称
char a[10][10],c='A'; int n=7; for(int i=1; i<=(n+1)/2; i++) { for(int j=1; j<=(n+1)/2; j++) { a[i][j]=a[i][n-j+1]=a[n-i+1][j]=a[n-i+1][n-j+1]=c++; } }上述代码将a[i][j]a[i]**[j]**数组赋值为：
A B C D C B A E F G H G F E I J K L K J I M N O P O N M //对称轴 I J K L K J I E F G H G F E A B C D C B A 对称轴3、不等值对称原理
很多时候我们理解对称是指，两个元素根据某对称轴(点)，两个数值完全等值对称，但有时候对称原理也可以应用到不等值的地方，例如根据对称轴(点)对称的两数的和(差)为固定值，那么只要知道这个对称公式，就可以来利用对称原理来进行快速赋值。
例如上图的一维数值赋值，可以写成如下形式：
int n=10,k=0,a[15]={0}; for(int i=1;i<=n/2;i++){//少循环一半 a[i]=i; a[n-i+1]=n+1-a[i]; } for(int i=1;i<=n;i++){//倒序遍历输出 cout<<a[i]<<" "; }上面的例子，就是利用不等值对称原理，让赋值的时间复杂度少了一半。
因为我们知道a[i]a[i]和a[n−i+1]a[n−i+1]关于中心点对称，且a[i]+a[n−i+1]=n+1a[i]+a[n−i+1]=n+1; 所以填完a[i]a[i]，即可直接求得a[n−i+1]=n+1−a[i]a[n−i+1]=n+1−a[i];
本章的方阵填数，大部分都可以用这节的数组对称规则来进行优化，但本文目的在于学习讨论各种规律特性，所以在其他节可能并没有利用对称原理优化，请大家自行思考是否可以利用对称原理来进行优化。
参考例题：
四、二维数组环形规律
int a[10][10],n=7,cnt=0; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { int t=min({i,j,n-i+1,n-j+1}); a[i][j]=t; } }上述代码将a[i][j]a[i]**[j]**数组赋值为：
1 1 1 1 1 1 1 1 2 2 2 2 2 1 1 2 3 3 3 2 1 1 2 3 4 3 2 1 1 2 3 3 3 2 1 1 2 2 2 2 2 1 1 1 1 1 1 1 1根据二维数组的环形规则，只要给定 (i,j)(i,j) 即可立刻定位到对应的位置，定位规则如下：
环形值t=min(i,j,n−i+1,n−j+1)t=min(i,j,n−i+1,n−j+1)；
第 tt 环的边长 =n−2∗(t−1)=n−2∗(t−1)；
if(it)if**(it)**则该点在上边；
if(jn−t+1)if**(jn−t+1)**则该点在右边；
if(in−t+1)if**(in−t+1)**则该点在下边；
if(jt)if**(jt)**则该点在左边；
习题
五、二维数组旋转规律
根据上述规律可得： 向右旋转 90°90° 或者向左旋转 270°：(i′=j,j′=n−i+1)270°：(i′=j,j′=n−i+1) 向右选择 180°180° 或者向左旋转 180°：(i′′=j′=n−i+1,j′′=n−i′+1=n−j+1)180°：(i′′=j′=n−i+1,j′′=n−i′+1=n−j+1) 向右旋转 270°270°或者向左旋转 90°：(i′′′=j′′=n−j+1,j′′′=n−i′′+1=n−(n−i+1)+1=i)90°：(i′′′=j′′=n−j+1,j′′′=n−i′′+1=n−(n−i+1)+1=i)
#include <bits/stdc++.h> using namespace std; void print(int x[][10],int n,int m) {//输出数组x[][] for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { cout<<setw(3)<<x[i][j]; } cout<<endl; } cout<<endl; } int main() { int a[10][10],b[10][10],c[10][10],n=5,m=5,k=0; cin>>n>>m; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { a[i][j]= ++k; b[j][n-i+1]=k;//向右旋转 c[m-j+1][i]=k;//向左旋转 } } print(a,n,m);//输出数组a[][] print(b,m,n);//输出数组b[][] print(c,m,n);//输出数组c[][] return 0; }上述代码运行的输出结果为：
5 7 //输入5行7列矩阵 1 2 3 4 5 6 7 //a[][]数组 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 29 22 15 8 1 //a[][]往右翻转后得到的b[][]数组 30 23 16 9 2 31 24 17 10 3 32 25 18 11 4 33 26 19 12 5 34 27 20 13 6 35 28 21 14 7 7 14 21 28 35 //a[][]往左翻转后得到的c[][]数组 6 13 20 27 34 5 12 19 26 33 4 11 18 25 32 3 10 17 24 31 2 9 16 23 30 1 8 15 22 29参考例题：
LQ1605CM5X. 矩阵圈层交错旋转(数据加强版）
六、其他填数规律
1、螺旋填数
a) 步行模拟法：
可以用模拟步行的算法进行填写：
//螺旋填数 模拟法 #include <bits/stdc++.h> using namespace std; int a[105][105]; int main(){ int n; cin>>n; //定义起点 int i=1,j=1;//起点坐标 int cnt=1; //起点数值 a[i][j]=cnt;//填写起点 while(cnt<n*n){//当cnt小于n*n则继续填写 //while(cnt<n*n-cnt+1){//从cnt~n*n+cnt-1填数 //while(下一个格子没有出界&&没有填数)//i,j-> i-1,j while(j+1<=n && a[i][j+1]==0)a[i][++j]=++cnt;//往右 while(i+1<=n && a[i+1][j]==0)a[++i][j]=++cnt;//往下 while(j-1>=1 && a[i][j-1]==0)a[i][--j]=++cnt;//往左 while(i-1>=1 && a[i-1][j]==0)a[--i][j]=++cnt;//往上 } //输出 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cout<<setw(3)<<a[i][j]<<" "; }cout<<endl; } return 0; }上述输出结果为：
5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9上述代码只需要更改起点信息，和移动方向，即可生成各种回型图
//回形填数 #include <bits/stdc++.h> using namespace std; int a[105][105],s,cnt;//s:起点数值 cnt:计数值 int main(){ int n; cin>>n>>s; //定义起点 int i=n,j=1;//起点坐标 a[i][j]=cnt=s;//填写起点 //while(cnt<n*n){//当cnt小于n*n则继续填写 while(cnt<n*n+s-1){//从cnt~n*n+cnt-1填数 //while(下一个格子没有出界&&没有填数)//i,j-> i-1,j while(i-1>=1 && a[i-1][j]==0)a[--i][j]=++cnt;//往上 while(j+1<=n && a[i][j+1]==0)a[i][++j]=++cnt;//往右 while(i+1<=n && a[i+1][j]==0)a[++i][j]=++cnt;//往下 while(j-1>=1 && a[i][j-1]==0)a[i][--j]=++cnt;//往左 } //输出 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cout<<setw(3)<<a[i][j]; }cout<<endl; } return 0; }上述输出结果为：
5 11 15 16 17 18 19 14 29 30 31 20 13 28 35 32 21 12 27 34 33 22 11 26 25 24 23b) 坐标法
令当前坐标位置为 (x,y)(x,y) ,则它的右，下，左，上的坐标分别是 (x,y+1)(x,y+1)，(x+1,y)(x+1,y)，(x,y−1)(x,y−1)，(x−1,y)(x−1,y)。
//螺旋填数 坐标法 #include <bits/stdc++.h> using namespace std; int a[105][105],n; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; int main(){ memset(a,-1,sizeof(a));//设置矩阵围墙，防止出界 cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ a[i][j]=0;//初始化 } } int x=1,y=1;//起点坐标 int d=0;//起始方向 for(int k=1;k<=n*n;k++){ a[x][y]=k; if(a[x+dx[d]][y+dy[d]]!=0)d=(++d)%4;//遇到不能填数了，则转向 x+=dx[d];//朝着下一个d方向填数 y+=dy[d]; } //输出 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cout<<setw(3)<<a[i][j]; }cout<<endl; } return 0; }c) 利用二维数组环形规律填数
//螺旋填数 环形规则 #include <bits/stdc++.h> using namespace std; int n,a[105][105],s,cnt;//cnt:计数值 int main(){ cin>>n; s=(n+1)/2;//环总数 for(int t=1;t<=s;t++){//t:环的序号 int len=n-(t-1)*2-1; //第t环的边长 if(len==0)len++;//最内圈如果为1个数的时候上一行求得的len会得0，所以需要+1； int x=t,y=t;//每一圈的起点位置 for(int i=1;i<=len;i++){//第一条上边长：往右走的边长 a[x][y++]=++cnt; } for(int i=1;i<=len;i++){//第二条右边长：往下走的边长 a[x++][y]=++cnt; } for(int i=1;i<=len;i++){//第三条下边长：往左走的边长 a[x][y--]=++cnt; } for(int i=1;i<=len;i++){//第四条左边长：往往走的边长 a[x--][y]=++cnt; } //上面四条边可以写成一个for循环 } //输出 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cout<<setw(3)<<a[i][j]; }cout<<endl; } return 0; }上述输出结果为：
5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9d) 公式法
螺旋方阵填数的最高效填法为：利用环形规则，根据给定的坐标 (i,j)(i,j) 直接即可计算得出该点的数值。
如上图所示，令i=7,j=6i=7,j=6，根据(i,j)**(i,j)**的值可以求得：
该点所在的环数 t=min({i,j,n−i+1,n−j+1})=3t=min({i,j,n−i+1,n−j+1})**=**3；
环的边长len=n−(t−1)×2−1;len=n−(t−1)×2−1; 得len=4;len=4;(注意如果是最里面的中心圈是否需要特判的情况)
这里讨论的边长len见下图中的图示范围，即为实际边长-1;
如果知道第tt环的起点或者终点数值，然后再求得(i,j)(i,j)在该环上的增量值dd；那么就可以直接求得a[i][j]a[i][j]。
那如何求得第tt环的起点或者终点值呢？
第一种方法：递推法求环的起点和终点值
int st[105] {0},endd[105]= {0},len; //st[t]:表示第t环的第一个数 //endd[t]:表示第t环的最后一个数 st[1]=1; for(int t=1; t<=(n+1)/2; t++) { len=n-(t-1)*2-1;//边长 st[t+1]=st[t]+len*4; //endd[t]=st[t+1]-1; } for(int t=1; t<=n/2; t++) { len=n-(t-1)*2-1;//边长 endd[t]=end[t-1]+len*4; //st[t+1]=endd[t]+1; }第二种方法：公式法求环的起点或者终点值
根据上图可知：
设第11圈的边长为 k=len1=n−1k=len1=n−1;
设填完tt圈后的最后一个数为end[t]end[t]：
end[t]=end[t]=第11圈总数++第22圈总数++第33圈总数+...++...+第tt圈总数
=(k−0)×4+(k−2)×4+(k−4)×4+...+(k−2×(t−1))×4**=(k−0)×4+(k−2)×4+(k−4)×4+...+(k−2×(t−1))**×4
=[k−0+k−2+k−4+k−2×(t−1)]×4**=[k−0+k−2+k−4+k−2×(t−1)]**×4
=[k×t−(0+2+4+2×(t−1))]×4**=[k×t−(0+2+4+2×(t−1))]×**4
=4×t×(k−t+1)=4×t×(k−t+1)
=4×t×(n−t)=4×t×(n−t)
第t+1t+1圈开始的第一个数为：st[t+1]=end[t]+1=4×t×(n−t)+1st**[t+1]=end**[t]+1=4×t×(n−t)**+**1
接下来求a[i][j]a[i][j]在第t环上的顺序偏移量dd值：
int t=min({i,j,n-i+1,n-j+1});//t环由外而内的序号 int len=n-(t-1)*2-1;//a[i][j]//所在环的边长 if(i==min(t,n-t+1)&&j<n-t+1) { //该点位于上面的绿色边上 d=j-i+1;//d=j-t+1;//t==i } if(i==max(t,n-t+1)&&j>t) { //该点位于下面的橙色边上 d=len*2+i-j+1;//d=len*2+(n-t+1)-j+1;//n-t+1==i } if(j==min(t,n-t+1)&&i>t) { //该点位于左面的红色边上 d=len*3+(n-j+1)-i+1;//d=len*3+(n-t+1)-i+1;//t==j } if(j==max(t,n-t+1)&&i<n-t+1) { //该点位于右面的蓝色边上 d=len+i-t+1;//t==n-j+1 }综上，a[i][j]=end[t−1]+d=4×(t−1)×(n−t+1)+da[i][j]=end[t−1]+d=4×(t−1)×(n−t+1)**+**d;
代码实现如下：
//螺旋填数 公式法 #include <bits/stdc++.h> using namespace std; int n,a[105][105],t,len,s,d,endd,st;//cnt:计数值 int main() { cin>>n; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { t=min({i,j,n-i+1,n-j+1});//t:环由外而内的序号 len=n-(t-1)*2-1;//a[i][j]//所在环的边长 endd=4*t*(n-t);//第t圈结束的值 st=endd-len*4;//第t-1圈结束的值 //求在t环上的偏移量d值 d=1;//当n为奇数时候，考虑中心点时候下面if语句d值不计算，所以初始化为1 //此时也可以把求d值的if语句中的 && j<n-t+1 &&j>t &&i<n-t+1删除，但是&&i>t不能删除 if(i==min(t,n-t+1)&&j<n-t+1) { //该点位于上面的绿色边上 d=j-i+1;//d=j-t+1;//t==i } if(i==max(t,n-t+1)&&j>t) { //该点位于下面的橙色边上 d=len*2+i-j+1;//d=len*2+(n-t+1)-j+1;//n-t+1==i } if(j==min(t,n-t+1)&&i>t) { //该点位于左面的红色边上 d=len*3+(n-j+1)-i+1;//d=len*3+(n-t+1)-i+1;//t==j } if(j==max(t,n-t+1)&&i<n-t+1) { //该点位于右面的蓝色边上 d=len+i-t+1;//t==n-j+1 } a[i][j]=st+d; } } //输出 for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { cout<<setw(3)<<a[i][j]; } cout<<endl; } return 0; }以上代码运行结果：
5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9利用数组对称规则，可以让代码变得更简洁，我们先观察以下代码运行后的结果：
//螺旋填数 #include <bits/stdc++.h> using namespace std; int n,a[105][105],t,len,s,d,endd,st;//cnt:计数值 int main() { cin>>n; for(int i=1; i<=(n+1)/2; i++) { for(int j=i; j<=n-i+1; j++) { t=min({i,j,n-i+1,n-j+1});//t:环由外而内的序号 len=n-(t-1)*2-1;//a[i][j]//所在环的边长 endd=4*t*(n-t);//第t圈结束的值 st=endd-len*4;//第t-1圈结束的值 d=j-i+1;//偏移量d值 a[i][j]=st+d; } } //输出 for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { cout<<setw(3)<<a[i][j]; } cout<<endl; } return 0; }以上代码运行结果：
5 1 2 3 4 5 0 17 18 19 0 0 0 25 0 0 0 0 0 0 0 0 0 0 0 0如果第9行改为j<=n−ij<=n−i，则运行结果为：
5 1 2 3 4 0 0 17 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0我们只需要计算出上面1/4部分的数据，其他3/4部分可以利用对称规律直接得出：
//螺旋填数 #include <bits/stdc++.h> using namespace std; int n,a[105][105],t,len,s,d,endd,st;//cnt:计数值 int main() { cin>>n; for(int i=1; i<=(n+1)/2; i++) { for(int j=i; j<=n-i+1; j++) { t=min({i,j,n-i+1,n-j+1});//t:环由外而内的序号 len=n-(t-1)*2-1;//a[i][j]//所在环的边长 endd=4*t*(n-t);//第t圈结束的值 st=endd-len*4;//第t-1圈结束的值 d=j-i+1;//偏移量d值 a[i][j]=st+d;//上面的绿色边 //利用对称规律直接得出剩下三个数 a[j][n-i+1]=st+len+d;//右面的蓝色边 a[n-i+1][n-j+1]=st+len*2+d;//下面的橙色边 if(i+j!=n+1){//思考：如果没有这句会怎样？ a[n-j+1][i]=st+len*3+d;//左面的红色边 } } } //输出 for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { cout<<setw(3)<<a[i][j]; } cout<<endl; } return 0; }第9行如果jj循环少一次，则可以改写为：
//螺旋填数 #include <bits/stdc++.h> using namespace std; int n,a[105][105],t,len,s,d,endd,st;//cnt:计数值 int main() { cin>>n; for(int i=1; i<=(n+1)/2; i++) { for(int j=i; j<=n-i; j++) {//比上面代码少循环一次 t=min({i,j,n-i+1,n-j+1});//t:环由外而内的序号 len=n-(t-1)*2-1;//a[i][j]//所在环的边长 endd=4*t*(n-t);//第t圈结束的值 st=endd-len*4;//第t-1圈结束的值 d=j-i+1;//偏移量d值 a[i][j]=st+d;//上面的绿色边 //利用对称规律直接得出剩下三个数 a[j][n-i+1]=st+len+d;//右面的蓝色边 a[n-i+1][n-j+1]=st+len*2+d;//下面的橙色边 a[n-j+1][i]=st+len*3+d;//左面的红色边 } } a[(n+1)/2][(n+1)/2]=n*n;//当n为奇数时候，最后一圈要单独赋值 //输出 for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { cout<<setw(3)<<a[i][j]; } cout<<endl; } return 0; }例题：
2、S形填数
S形如下图：
1、模拟法
模拟法1
//起点位线内 #include <bits/stdc++.h> using namespace std; int n,a[105][105],x,y,k; int main(){ cin>>n; x=1;y=1;k=1;a[x][y]=k; while(k<n*n){ while(x-1>=1 && y+1<=n)a[--x][++y]=++k;//往右上 if(x+y<=n)a[x][++y]=++k; else a[++x][y]=++k; while(x+1<=n && y-1>=1)a[++x][--y]=++k;//往左下 if(x+y<=n)a[++x][y]=++k; else a[x][++y]=++k; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cout<<setw(3)<<a[i][j]; } cout<<endl; } return 0; }模拟法2
////起点位线外 #include <bits/stdc++.h> using namespace std; int a[105][105],n; int main(){ cin>>n; int i=0,j=1,k=0; //起点 //int n,i=1,j=1,k=1; a[1][1]=k;//起点 while(k<n*n){ if(i+j<n+1){ i+=2;j--; }else{ i++; } while(i-1>=1 && j+1<=n) a[--i][++j]=++k; //往右上 if(i+j<n+1){ i--;j+=2; }else{ j++; } while(i+1<=n && j-1>=1) a[++i][--j]=++k; //往右上 } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cout<<setw(3)<<a[i][j]; } cout<<endl; } return 0; }2、对角线原理填数
利用对角线原理遍历填数1
#include <bits/stdc++.h> using namespace std; int a[55][55],n,cnt=0; int main() { cin>>n; for(int p=1;p<=2*n-1;p++){//右斜对角线 p: i+j=1 int m,i,j;//对角线长度为m，坐标(i,j) if(p<=n){//对角线p左上角 m=p;i=p;j=1;//起点坐标(i,j) }else{//对角线p右下角 m=2*n-p;i=n;j=p-n+1;//起点坐标(i,j) } for(int q=1;q<=m;q++){//每条对角线的长度为 m if(p%2)a[i--][j++]=++cnt;//p奇数则左下往右上方向填数 else a[j++][i--]=++cnt;//p偶数则右上往左下方向填数 } } //输出 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cout<<setw(3)<<a[i][j]; } cout<<endl; } return 0; }利用对角线原理遍历填数2
#include <bits/stdc++.h> using namespace std; int i,j,n,m,a[20][20] = {0},t=0; int main(){ cin>>n; for(i = 1;i<=2*n-1;i++){//斜向的行数i if(i<=n)m=i; //左上角 else m=n-i%n; //右下角 for(j = 1;j <=m;j++){//斜向的列数j m=1,2...n...2,1; if(i<=n){//填写左上角 if(i%2){ a[i-j+1][j]=++t;//奇数行 }else{ a[j][i-j+1] = ++t;//偶数行 } } else{//填写右下角 if(i%2){ a[n-j+1][i%n+j]=++t;//奇数行 }else{ a[i%n+j][n-j+1]=++t;//偶数行 } } } } //输出 for(i = 1;i <= n;i++){ for(j = 1;j <= n;j++){ cout<<setw(3)<<a[i][j]; } cout<<endl; } return 0; }3、公式法
全网最高效解法：直接计算求解
#include <bits/stdc++.h> using namespace std; int n,a[20][20] = {0},k,s=0; int main(){ cin>>n; for(int i=1;i<=n;i++){//第i行 for(int j=1;j<=n;j++){//第j列 k=i+j-1;//右斜对角线序号k if(k>n){//右下角 //求k行之前已经填写的个数总和，即s=1+2+3+...+n+(n-1)+...+(2*n-k); s=n*n-(1+(2*n-1-k+1))*(2*n-1-k+1)/2; if(k%2) a[i][j]=s+j-k%n;//奇数行计算公式 else a[i][j]=s+i-k%n; //偶数行计算公式 }else{//左上角 //求k行之前已经填写的个数总和，即s=1+2+3+...+(k-1) s=(1+(k-1))*(k-1)/2; if(k%2) a[i][j]=s+j;//奇数行计算公式 else a[i][j]=s+i;//偶数行计算公式 } } } //输出 for(int i = 1;i <= n;i++){ for(int j = 1;j <= n;j++){ cout<<setw(3)<<a[i][j]; } cout<<endl; } return 0; }上述代码如果利用不等值对称原理进行优化，将使问题变得更简单：
我们只需要考虑填写左上角数值，然后右下角数值可以直接利用对称原理求得。
优化后的代码：
#include <bits/stdc++.h> using namespace std; int n,a[20][20] = {0},k,s=0; int main(){ cin>>n; for(int i=1;i<=n;i++){//第i行 for(int j=1;j<=n-i+1;j++){//第j列 k=i+j-1;//右斜对角线序号k //求k行之前已经填写的个数总和， //即s=1+2+3+...+(k-1)=(1+(k-1))*(k-1)/2=k*(k-1)/2; s=k*(k-1)/2; a[i][j]=s+!(k%2)*i+(k%2)*j; a[n-i+1][n-j+1]=n*n+1-a[i][j]; } } //输出 for(int i = 1;i <= n;i++){ for(int j = 1;j <= n;j++){ cout<<setw(3)<<a[i][j]; } cout<<endl; } return 0; }/*第12行代码的解释 if(k%2){ a[i][j]=s+j;//奇数行计算公式 a[n-i+1][n-j+1]=n*n+1-a[i][j];//利用对称原理填写右下角的值 }else{ a[i][j]=s+i;//偶数行计算公式 a[n-i+1][n-j+1]=n*n+1-a[i][j];//利用对称原理填写右下角的值 } */例题：
- 1
