《蛇形矩阵》及常见偏移量拓展!!使用非常巧妙的方式~
题目描述:
输入两个整数 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
偏移量技巧:
在进行矩阵四个方向的表示时,可以使用for循环+偏移量来表示四个方向。用两个数组记录四个方向。dx = {-1, 0, 1, 0},dy = {0, 1, 0, -1}
用(-1, 0)代表上方向,用(0, 1)代表右方向,用(1, 0)代表下方向,用(0, -1)代表左方向。
注:图片来源于y总
那么怎么表示向一个方向走呢?可以使用坐标+一个向量表示。(x, y) + dx[d], dy[d]
,即x = x + dx[d],y = y + dy[d]
。开始初始化d = 1, 即表示向右走。
判断 :如果遇到边界或已经放过数字了,改变方向。按照顺时针方向来改变,刚好符合我们的数组的四个值。
那么怎么改变方向呢?每次撞墙要改变方向,都可以用d = (d + 1) % 4
来实现。
偏移量技巧有很多应用:宽搜,FloodFill(洪水灌溉)算法。
java代码参考:
import java.util.Scanner;
public class Main {
static int N = 110;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] dx = {-1, 0, 1, 0}; // 分别对应上右下左
int[] dy = {0, 1, 0, -1};
int[][] q = new int[N][N];
//用x, y记录走到了哪个位置,初始为q[0][0]
int x = 0, y = 0, d = 1;
for (int i = 1; i <= n * m; i++) {
q[x][y] = i;
//用a 和 b 来表示下一个要走到的位置
int a = x + dx[d];
int b = y + dy[d];
//如果a, b不符合,则d ++,更换方向!
if(a < 0 || a >= n || b < 0 || b >= m || q[a][b] > 0){
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++) {
System.out.print(q[i][j] + " ");
}
System.out.println();
}
}
}
偏移量问题拓展:
- 马走日问题(八个方向)
- 拓展旁边八个格子
注:此类问题也可以使用双循环解决。