基础算法-模拟：蛇形方阵

P5731 【深基5.习6】蛇形方阵题目链接:P5731 【深基5.习6】蛇形方阵 - 洛谷这个题目解法很多可以用几个循环嵌套解决也可以用一个循环加上很多个if-else判断解决但是这些解法很不适用我们可以用另外一种方式来解决该题如果学会了这种方式以后90%以上矩阵和数组的题目都可以用这种方式来解决。定义方向向量我们可以把这个数字的行走过程看成一个坐标系从0,0---0,1---0,2构建出如图的坐标系我们可以发现按照顺时针方向走先是往右走再是往下走再是往左走再是往上走这种方式而往右走相当于把原坐标加上(0,1)向下走相当于把原坐标加上(1,0)向左走相当于把原坐标加上(0,-1)向上走相当于把原坐标加上(-1,0)。也就是说我们可以定义两个数组来模拟方向向量一个数组为dx另外一个为dy这个用dx[i],dy[i]就是方向向量因为我们每一步都是通过原坐标加上方向向量而来所以我们可以把这个矩阵问题近似看为一个坐标加上对应的方向向量得到下一个坐标的问题。接下来就是根据规则结合方向向量填数从1,1作为起始位置1朝一个方向走一边走一边填数直到越界2越界之后结合方向向量重新计算出新的坐标及方向。我们填到4的时候坐标为(1,4)但是我们发现如果用方向向量推出下一个位置1,5此时就会越界了因此我们需要改变方向向量我们可以设定一个pos开始pos为0每次要移动时先判断是否越界如果越界则用pos(pos1)%4得到下一个位置然后再用这个方向向量得到下一个正确的坐标#includeiostream using namespace std; //方向向量 int dx[] { 0 ,1 ,0 ,-1 }; int dy[] { 1 ,0 ,-1 ,0 }; // 右 下 左 上 //设置N最大值为100n9但是我们是从下标为1开始的方便理解所以要把N设置成10 const int N 10; //定义最终的数组 int arr[N][N]; int main() { int n; cin n; //模拟填数过程 int x 1, y 1; int cnt 1;//当前位置需要填的数 int pos 0;//当前的方向向量对应的位置 while (cnt n * n) { arr[x][y] cnt; //计算下一个位置 int a x dx[pos], b y dy[pos]; //判断是否越界 if (a n) { //更新出正确的位置 pos (pos 1) % 4; a x dx[pos], b y dy[pos]; } } return 0; }这就是我们初始代码但是我们还要再分清楚其他边界情况当我们往下走到5,4即xn的时候也越界了当我们往左走到40即y1也越界了因为我们是从下标为1开始进行填写的所以我们不能把这个数写到横坐标或纵坐标为0的那一行和一列当我们往上走到1,1这个时候这个位置已经填入了数据也相当于越界了这个时候我们可以用arr[a][b] ! 0来判断这种边界情况更新以后代码变成这样#includeiostream using namespace std; //方向向量 int dx[] { 0 ,1 ,0 ,-1 }; int dy[] { 1 ,0 ,-1 ,0 }; // 右 下 左 上 //设置N最大值为100n9但是我们是从下标为1开始的方便理解所以要把N设置成10 const int N 10; //定义最终的数组 int arr[N][N]; int main() { int n; cin n; //模拟填数过程 int x 1, y 1; int cnt 1;//当前位置需要填的数 int pos 0;//当前的方向向量对应的位置 while (cnt n * n) { arr[x][y] cnt; //计算下一个位置 int a x dx[pos], b y dy[pos]; //判断是否越界 if (a n || a 1 || b n || b 1 || arr[a][b] ! 0) { //更新出正确的位置 pos (pos 1) % 4; a x dx[pos], b y dy[pos]; } //更新x,y x a, y b; //更新cnt cnt; } return 0; }最后再按照题目的格式进行输出即可#includeiostream using namespace std; //方向向量 int dx[] { 0 ,1 ,0 ,-1 }; int dy[] { 1 ,0 ,-1 ,0 }; // 右 下 左 上 //设置N最大值为100n9但是我们是从下标为1开始的方便理解所以要把N设置成10 const int N 10; //定义最终的数组 int arr[N][N]; int main() { int n; cin n; //模拟填数过程 int x 1, y 1; int cnt 1;//当前位置需要填的数 int pos 0;//当前的方向向量对应的位置 while (cnt n * n) { arr[x][y] cnt; //计算下一个位置 int a x dx[pos], b y dy[pos]; //判断是否越界 if (a n || a 1 || b n || b 1 || arr[a][b] ! 0) { //更新出正确的位置 pos (pos 1) % 4; a x dx[pos], b y dy[pos]; } //更新x,y x a, y b; //更新cnt cnt; } //输出 for (int i 1; i n; i) { for (int j 1; j n; j) { printf(%3d, arr[i][j]); } cout \n; } return 0; }