欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

跳n*n的方格,每个方格数字是1~k,找到一条路径(1~k),且|x1-x2|+|y1-y2|最小,时间复杂度(On2)

程序员文章站 2022-07-12 22:49:37
...
/**
  * 跳n*n的方格,每个方格数字是1~k,找到一条路径(1~k),且|x1-x2|+|y1-y2|最小,时间复杂度(On2)
  * @param
  * @return
  */
 public class main {
     public static void main(String[] args) {
         Scanner in = new Scanner(System.in);
         while (in.hasNext()){
             int n = in.nextInt();
             int k = in.nextInt();
             int[][] box = new int[n][n];
             if (n>=1&&n<=50&&k>=1&&k<=n*n){
                 for(int i=0;i<n;i++){
                     int j = 0;
                     while (j<n){
                         box[i][j] = in.nextInt();
                         if(box[i][j]>=1&&box[i][j]<=k){
                             j++;
                         }
                     }
                 }
                 int min_distance = minDistance(box, n, k);
                 System.out.print(min_distance);
             }
             System.out.println();
         }
     }

     public  static int minDistance(int[][] box, int n, int k){
         boolean flag = false;//方格开始是否遍历到1~k
         int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
         int x1 = -1, y1 = -1, x2 = -1, y2 = -1;
         int min_distance = MAX_VALUE;
         for (int i=0;i<n;i++){ //遍历每个方格
             for (int j=0;j<n;j++){
                 x1 = i;
                 y1 = j;
                 int p = 2;
                 if(box[i][j]==1){ //判断当前方格是否为1
                     x2 = i;
                     y2 = j;
                     while (p<=k){
                         int temp = p;
                         for (int q=0;q<directions.length;q++){ //上下左右移动
                             x2 = x2 + directions[q][0];
                             y2 = y2 + directions[q][1];
                             if(x2>=0&&x2<n&&j+y2>=0&&j+y2<n){//判断是否越界
                                 if(box[x2][y2]==p){
                                     p++;
                                     break;
                                 }
                             }
                             x2 = x2 - directions[q][0]; //若越界或不为p,则后退
                             y2 = y2 - directions[q][1];
                         }
                         if(temp==p){   //若访问上下左右p未变
                             x2 = i;
                             y2 = j;
                             break;
                         }
                     }
                 }
                 if(p == k+1){  //若有按顺序遍历完1~k,则表示有distance,计算最小距离
                     flag = true;
                     int distance = Math.abs(x1-x2)+Math.abs(y1-y2);
                     if(distance<min_distance){
                         min_distance = distance;
                     }
                 }
             }
         }
     if(flag == true){ //若有遍历完1~k
             return min_distance;
         }else {
             return -1;
         }
     }
}

 

相关标签: leetcode