04-蛇形矩阵的快速解法

题目描述

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

解题思路

• 该题的本质其实是找坐标，值直接用循环就可以表示出。
• 本题目会用到偏移量技巧
  

代码

#include <iostream>
#include <cstdio>
using namespace std;
int res[100][100]; 

int main()
{

	int n,m;
	cin >> n >> m;
	
	int dx[] = {0,1,0,-1},dy[] = {1,0,-1,0};
	
	for (int x = 0,y = 0,d = 0, k=1;k <= n*m;k++)
	{
		res[x][y] = k;
		int a = x + dx[d],b = y + dy[d];  //找坐标 
	    if (a < 0 || a >= n || b < 0 || b >= m || res[a][b]) //判断是否越界以及方向是否走过 
		{
			d = (d+1) % 4;
			a = x + dx[d],b = y + dy[d];
		} 
		x = a,y = b;
	}
	
	for (int i = 0;i < n;i++)
	{
		for (int j = 0;j < m;j++) cout << res[i][j] << ' ';
		cout << endl;
	}
	
	return 0;
 }