AcWing 756. [Java]蛇形矩阵(走迷宫解法?)
原题链接
简单
作者:
寒星hanxing
,
2021-01-11 21:16:30
,
所有人可见
,
阅读 8
Java 代码
//与LeetCode螺旋矩阵几差不多,修改了下输入输出……
//走迷宫,碰壁就走下一个方向,方向选择固定→↓←↑
import java.util.Scanner;
class Main {
private int[][] generateMatrix(int n, int m) {
int[][] result = new int[n][m];
spiralOrder(result);
return result;
}
private void spiralOrder(int[][] matrix) {
int row = matrix.length;
int col = matrix[0].length;
boolean[][] isPath = new boolean[row][col];//标记数组,标记已经走过的路
int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//方向数组,4个方向顺序固定
matrix[0][0] = 1;
isPath[0][0] = true;
int i = 1, r = 0, c = 0, d = 0;
while (i < row * col) {
if (r == 0 && d == 3 || r == row - 1 && d == 1 ||
c == 0 && d == 2 || c == col - 1 && d == 0) {//边界碰壁.换个方向
d++;
d %= 4;
} else {
if (isValid(isPath[r + dir[d][0]][c + dir[d][1]], r, c, row, col)) {//标记碰壁,换个方向
++i;
matrix[r + dir[d][0]][c + dir[d][1]] = i;
isPath[r + dir[d][0]][c + dir[d][1]] = true;
r += dir[d][0];
c += dir[d][1];
} else {
d++;
d %= 4;
}
}
}
}
private boolean isValid(boolean isPath, int r, int c, int row, int col) {//合法地行走
return r >= 0 && r < row && c >= 0 && c < col && !isPath;
}
public static void main(String[] args) {
Main acWing_0756_1 = new Main();
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[][] a = acWing_0756_1.generateMatrix(n,m);
for(int i =0; i < n; i++){
for(int j = 0; j < m; j++)
System.out.print(a[i][j]+" ");
System.out.println();
}
}
}