题目描述
蛇形矩阵(偏移量技巧)
算法1
(1)确定好行走路线的方向规律。上下左右 或者 其他
(2)对每个方向定义一个数。d = {0,1,2,3}, 知道 (d+1)%4 = d
(3)找出依路线行走时的坐标变换规律。dx[] = {-1, 0, 1, 0 } and dy[] = {0, 1, 0, -1 }。其中x和y和d都一一对应的
(4)找出“撞墙”的界限,包括出界or重复格。a<0 || a>=n || b<0 || b>=m || q[a][b]!=0
时间复杂度
JAVA 代码
import java.util.*;
public class Main{
static Scanner in = new Scanner(System.in);
public static void main(String[] args){
int n = in.nextInt();
int m = in.nextInt();
int[][] q = new int[n][m];
int[] dx = {-1, 0, 1, 0};
int[] 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 a = x + dx[d]; int b = y + dy[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();
}
}
}