我有一个m * n矩阵,其中每个元素都是唯一的。从给定的起点,我必须移到最小的点(上,下,左,右),然后再次执行相同的过程。当所有其他周围的点都大于现有的周围点时,我必须停止并从头开始打印位置。假设我有一个矩阵(5 * 5)
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
起始点为(2,2),则输出为
13,8,3,2,1
。我已经以自己的方式解决了这个问题,但是问题是它的复杂性。我认为我的解决方案不是有效的。谁能建议我更好的解决方案?
N.B:除扫描仪pkg外,我不允许导入其他任何pkg。这是我的代码:
import java.util.Scanner;
public class DirectionArray {
public static void main(String [] args) {
Scanner in = new Scanner(System.in);
int row = in.nextInt();
int col = in.nextInt();
int[][] ara = new int[row][col];
int[] ara2 = new int[4];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
ara[i][j] = in.nextInt();
}
}
System.out.println("Give starting point(x) ");
int x= in.nextInt();
System.out.println("Give starting point(y) ");
int y= in.nextInt();
int sx=x;
int sy =y;
int [] fx={+1,-1,0,0};
int [] fy={0,0,+1,-1};
int p=0;
int l=0;
int v=0;
int r=0;
int [] result=new int[row*col] ;
int min=ara[x][y];
boolean swap=true;
for(int i=0;i<(row*col)-1;i++) {
for (int k = 0; k < 4; k++) {
int nx = x + fx[k];
int ny = y + fy[k];
if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
if (min > ara[nx][ny]) {
ara2[p] = ara[nx][ny];
p++;
}
}
}
p=0;
while(swap) {
swap=false;
r++;
for (int q = 0; q < ara2.length-r; q++) {
if(ara2[q]>ara2[q+1]){
int temp = ara2[q];
ara2[q]=ara2[q+1];
ara2[q+1]=temp;
swap=true;
}
}
}
for(int j=0;j<ara2.length;j++) {
if(ara2[j]!=0)
{
v=ara2[j];
result[l]=v;
l++;
break;
}
}
min=v;
for(int o=0;o<ara2.length;o++) {
ara2[o]=0;
}
for(int m=0;m<row;m++){
for(int n=0;n<col;n++){
if(ara[m][n]==v) {
x = m;
y = n;
}
}
}
最佳答案
我认为您需要将代码拆分为更多方法。这将使其更易于阅读。
例如,这就是我将如何重组它:
private static final int[][] COORDINATES_TO_TRY = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int row = in.nextInt();
int col = in.nextInt();
int[][] array = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
array[i][j] = in.nextInt();
}
}
System.out.println("Give starting point(x) ");
int x = in.nextInt();
System.out.println("Give starting point(y) ");
int y = in.nextInt();
findMinimum(array, x, y);
return;
}
private static int[] findMinimum(int[][] array, int x, int y) {
for (int i = 0; true; i++) {
if (i > 0) {
System.out.print(",");
}
System.out.print(array[x][y]);
int[] coordinates = findLocalMinimum(array, x, y);
if (x == coordinates[0] && y == coordinates[1]) {
return coordinates;
}
x = coordinates[0];
y = coordinates[1];
}
}
private static int[] findLocalMinimum(int[][] array, int x, int y) {
int min = array[x][y];
int minX = x;
int minY = y;
for (int[] coordinates : COORDINATES_TO_TRY) {
int i = x + coordinates[0];
int j = y + coordinates[1];
if (i >= 0 && i < array.length && j >= 0 && j < array[i].length) {
if (array[i][j] < min) {
minX = i;
minY = j;
min = array[i][j];
}
}
}
return new int[]{minX, minY};
}
关于java - 方向阵列:降低复杂性,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/47654847/