外卖配送的路径规划 Krains 2021-04-09 BFS动态规划

我有个待购买的物品清单，假设我的位置在地图的左上角，规划一条路径，
使得在能够购买所有所需物品的前提下，所走的路径最短。

输入：
第一行一个数字n，代表物品清单有n件物品
第二行是代购买的物品清单
第三行有两个数字，row和col，代表地图的行数和列数
接下来有row行和col列，代表地图

3
a b c
5 6
0 0 0 a 0 d 
0 1 1 d 0 1 
0 1 b 0 0 0 
0 0 a 0 c 0 
c 1 0 0 1 b

ps: 1是障碍物，小红只能走上下左右四个方向

输出：我所走的最短路径的长度和及其对应的路径

public class Main {
    static String path = "D:\\workplace\\idea-project\\HdfsClientDemo\\src\\main\\resources\\input";
    static final int[] dx = new int[]{1, 0, -1, 0};
    static final int[] dy = new int[]{0, 1, 0, -1};
    
    class Node{
        int x;
        int y;
        int state;
        int step;
        
        Node(int x, int y, int state, int step){
            this.x = x;
            this.y = y;
            this.state = state;
            this.step = step;
        }

        @Override
        public String toString() {
            return x + "_" + y +"_" + state;
        }
    }
    
    static int whichGoods(char c){ 
        int i = c - 'a';
        if(i >= 0 && i < 26)
            return i;
        return -1;
    }
    
    public List<int[]> find(char[][] graph, Set<Character> list) {
        int target = 0;
        int num = list.size();
        int row = graph.length;
        int col = graph[0].length;
        boolean[][][] vis = new boolean[row][col][1 << num];
        Deque<Node> queue = new LinkedList<>();
        Map<String, String> path = new HashMap<>();
        int endX = -1;
        int endY = -1;
        // 遍历订单列表，获得目标状态
        for(char c : list){
            int i = whichGoods(c);
            if(i != -1){
                target |= (1 << i);
            }
        }
        int originState = 0;
        int originX = 0;
        int originY = 0;
        int goods = whichGoods(graph[originX][originY]);
        if(goods != -1 && list.contains(graph[originX][originY]))
            originState |= (1 << goods);
        vis[originX][originY][originState] = true;
        String start = originX + "_" + originY + "_" + originState;
        queue.add(new Node(originX, originX, originState, 0));
        while(queue.size() > 0){
            Node k = queue.remove();
            if(k.state == target){
                endX = k.x;
                endY = k.y;
                break;
            }
            for(int i = 0; i < 4; i++){
                int x = k.x + dx[i];
                int y = k.y + dy[i];
                int newState = k.state;
                int curStep = k.step;
                if(x >= row || x < 0 || y >= col || y < 0 || graph[x][y] == '1')
                    continue;
                goods = whichGoods(graph[x][y]);
                if(goods != -1 && list.contains(graph[x][y]))
                    newState |= (1 << goods);
                if(vis[x][y][newState] == false){
                    vis[x][y][newState] = true;
                    Node node = new Node(x, y, newState,curStep + 1);
                    path.put(node.toString(), k.toString());
                    queue.add(node);
                }
            }
        }
        List<int[]> ans = new ArrayList<>();
        if(endX == -1)
            return ans;
        String s = endX + "_" + endY + "_" + target;
        // System.out.println(s);
        while(s != null && !start.equals(s)){
            // System.out.println(s);
            String[] p = s.split("_");
            ans.add(new int[]{Integer.parseInt(p[0]), Integer.parseInt(p[1])});
            s = path.get(s);
        }
        ans.add(new int[]{0, 0});
        return ans;
    }
    
    public static void main(String[] args) throws IOException {
        File file = new File(path);
        Scanner scanner = new Scanner(file);
        int num = scanner.nextInt();
        scanner.nextLine();
        String[] goods = scanner.nextLine().split(" ");
        Set<Character> list = new HashSet<>();
        for(String good : goods){
            list.add(good.charAt(0));
        }
        int row = scanner.nextInt();
        int col = scanner.nextInt();
        char[][] graph = new char[row][col];
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                graph[i][j] = scanner.next().charAt(0);
            }
        }
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                System.out.print(graph[i][j] + " ");
            }
            System.out.println();
        }
        
        List<int[]> path = new Main().find(graph, list);

        System.out.println("最短路径长度：" + (path.size() - 1));
        System.out.println("路线如下：");
        for(int[] p : path){
            System.out.println(p[0] + " " +p[1]);    
        }
    }
}

3
a b c
5 6
0 0 0 a 0 d 
0 1 1 d 0 1 
0 1 b 0 0 0 
0 0 a 0 c 0 
c 1 0 0 1 b

0 0 0 a 0 d 
0 1 1 d 0 1 
0 1 b 0 0 0 
0 0 a 0 c 0 
c 1 0 0 1 b 
最短路径长度：8
路线如下：
2 2
3 2
3 1
3 0
4 0
3 0
2 0
1 0
0 0