华为上周五机试飞行路线问题求解答~~

import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in); while (scanner.hasNext()){ int x = scanner.nextInt(); int y = scanner.nextInt(); int[][] arr= {{0,2,10,5,3,1000},{1000,0,12,1000,1000,10},{1000,1000,0,1000,7,1000},
                {2,1000,1000,0,2,1000},{4,1000,1000,1,0,1000},{3,1000,1,1000,2,0}}; if (x==5){//为5时等于没走  System.out.println(0);
                System.out.println("[5]"); continue;
            } if(x==y){//不可达  System.out.println(1000);
                System.out.println("[]"); continue;
            } if (y!=0){ for (int i=0;i<6;i++){ if (i!=y-1){
                        arr[i][y-1]=1000;
                        arr[y-1][i]=1000;
                    }
                }
            } boolean[][] check=new boolean[6][6];
            ArrayList<String> list=new ArrayList<>();
            String time="";
            String path="5"; getMin(arr, check, 4, x - 1, time, path, list);
            System.out.println(list);
        }
    } public static ArrayList<String> getMin(int[][]arr,boolean[][]check,int x,int y,String time,String path,ArrayList<String> list){ if (x==y){
            list.add(time+" "+path); return list;
        } for (int i = 0; i < 6; i++) { if (x==i||arr[x][i]==1000||check[x][i]){ continue;
                }
                check[x][i]=true;
                path=path+","+(i+1);
                time=time+","+arr[x][i]; getMin(arr,check,i,y,time,path,list);
            } return list;
    }
} 输入4，6.结果为[,4,2,12,7,1 5,1,2,3,5,4, ,4,2,10,5 5,1,2,3,4]，

求解答后面的1，2，3，4这种情况怎么跑出来的。还有从5出发到4，
这种做法先5到1到2到3到5到4的话，会在标记已走的路线中标记5到4导致 直接从5到4的路线在后面被跳过，该如何解决？

全部评论

推荐最新楼层

妞客0111347号

Java

import java.util.ArrayList; import java.util.Scanner; import java.util.Stack; public class Main { public static int[][] maze = { {-1, -1, -1, -1, -1, -1, -1}, {-1, 0, 2, 10, 5, 3, -1}, {-1, -1, 0, 12, -1, -1, 10}, {-1, -1, -1, 0, -1, 7, -1}, {-1, 2, -1, -1, 0, 2, -1}, {-1, 4, -1, -1, 1, 0, -1}, {-1, 3, -1, 1, -1, 2, 0}}; public static int minDis = Integer.MAX_VALUE; public static ArrayList<Integer> result = null; public static void main(String[] args) { Main main = new Main(); Scanner scanner = new Scanner(System.in); int X = 0, Y = 0; while (scanner.hasNext()) { X = scanner.nextInt(); Y = scanner.nextInt(); Stack<Integer> path = new Stack<Integer>(); boolean[] visited = new boolean[7]; main.initVisited(visited); visited[5] = true; path.push(5); main.dfs(path, visited, 5, 0, X, Y); if (result == null) { System.out.println(1000); System.out.println(new ArrayList<Integer>()); } else { System.out.println(minDis); System.out.println(result); } minDis = Integer.MAX_VALUE; result = null; } } private void dfs(Stack<Integer> path, boolean[] visited, int currentCity, int distance, int target, int forbidden) { if (currentCity == target) { if (distance < minDis) { minDis = distance; result = new ArrayList<Integer>(); for (int i = 0; i < path.size(); i++) { result.add(path.get(i)); } } return; } for (int i = 1; i <= 6; i++) { if (visited[i]) { continue; } if (maze[currentCity][i] == -1) { continue; } if (currentCity == forbidden || i == forbidden) { continue; } path.push(i); visited[i] = true; dfs(path, visited, i, distance + maze[currentCity][i], target, forbidden); visited[i] = false; path.pop(); } } private void initVisited(boolean[] visited) { for (int i = 0; i < visited.length; i++) { visited[i] = false; } } }

华为上周五机试飞行路线问题求解答~~

全站热榜