PAT1050 螺旋矩阵 只能通过前三个测试点,求大佬指教
本题要求将给定的 N 个正整数按非递增的顺序,填入“螺旋矩阵”。所谓“螺旋矩阵”,是指从左上角第 1 个格子开始,按顺时针螺旋方向填充。要求矩阵的规模为 m 行 n 列,满足条件:m×n 等于 N;m≥n;且 m−n 取所有可能值中的最小值。
输入格式:
输入在第 1 行中给出一个正整数 N,第 2 行给出 N 个待填充的正整数。所有数字不超过 1,相邻数字以空格分隔。
输出格式:
输出螺旋矩阵。每行 n 个数字,共 m 行。相邻数字以 1 个空格分隔,行末不得有多余空格。
输入样例:
12 37 76 20 98 76 42 53 95 60 81 58 93
输出样例:
98 95 93 42 37 81 53 20 76 58 60 76
代码如下,采用碰壁就转变方向的方法
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
//建立一个二维数组,表示result数组对应位置的元素是否被填充过了
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String s1=br.readLine();
String s2=br.readLine();
int N=Integer.parseInt(s1);
String[] s=s2.split("\\s+");
Integer[] a=new Integer[N];
for(int i=0;i<a.length;i++) {
a[i]=Integer.parseInt(s[i]);
}
Arrays.sort(a,new comparatordaoxu());
int t=(int) Math.ceil(Math.sqrt(N));
int m=0,n=0;
while(t<N) {
if(N%t==0) {
m=t;
n=N/m;
break;
}
t++;
}
int[][] result=new int[m][n];
boolean[][] check=new boolean[m][n];
int x=0,y=0;//行号和列号
int i=0;
//right,down,left,up
int[] directionx= {0,1,0,-1};
int[] directiony= {1,0,-1,0};
int di=0;
while(i<N) {
result[x][y]=a[i++];
check[x][y]=true;
int ni=x+directionx[di],ny=y+directiony[di];//到头或指定位置有元素就转换方向
if(ny>=n||ni>=m||ny<0||ni<0||check[ni][ny]==true) {
di=(di+1)%4;
}
x+=directionx[di];
y+=directiony[di];
}
for(i=0;i<=m-1;i++) {
for(int j=0;j<n-1;j++) {
System.out.print(result[i][j]+" ");
}
System.out.print(result[i][n-1]);
System.out.println();
}
}
}
class comparatordaoxu implements Comparator<Integer>{
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
}