开宝箱

华为笔试真题 5月27号 非AI方向 300分题型

题目内容

考古队在古道中发现了一个神秘的宝箱，宝箱需要按特定顺序收集文物碎片才能解锁。请你在一个 $n\times m$ 的网格中行动：

• $0$ 表示可通行的空地
• $1$ 表示障碍物（无法通过）
• $2$ 表示起点
• $3$ 表示宝箱位置
• $4-9$ 表示文物碎片（数字代表碎片编号）
  考古队需从起点出发，按照序号依次收集碎片并进入宝箱。每移动 $1$ 格的单位时间消耗为 $1$，移动时不能斜向移动。若存在多条路径，需选择耗时最短的方案。
  注意点： $1$. 碎片必须按编号升序收集（如先收集 $4$ 再收集 $5$）。 $2$. 允许碎片编号不连续（举例：网格中只有 $4,6$ 两块碎片，也能打开宝箱） $3$. 碎片编号重复时需要都收集（举例：网格中有两块 $4$ 号碎片和一块 $5$ 号碎片，则要收集两块 $4$ 号碎片和一块 $5$ 号碎片才能打开宝箱），每个碎片重复次数上限为 $3$。 $4$. 网格的最大为 $20\times 20$。 $5$. 保证存在至少一条有效路径，障碍物必须绕行，碎片等障碍物地点均可通行。

输入描述

• 第一行：$n$ 和 $m$
• 后续 $n$ 行：每行 $m$ 个整数，表示网格状态

输出描述

输出最短的总耗时

样例1

输入

4 5
2 0 0 0 0
1 0 4 0 0
1 0 1 5 0
1 0 1 1 3

输出

7

说明
起点位置(0,0)到碎片 $4(1,2)$ 最短耗时： $3$；
碎片 $4(1,2)$ 到碎片 $5(2,3)$ 最短耗时： $2$；
碎片 $5(2,3)$ 到宝箱 $(3,4)$ 最短耗时： $2$；
总计耗时：$3+2+2=7$

样例2

输入

5 5
0 2 0 0 0
0 1 0 4 0
0 1 0 1 5
0 1 0 6 1
0 1 0 0 3

输出

13

说明
起点位置 $(0,1)$ 到碎片 $4(1,3)$ 最短耗时： $3$；
碎片 $4(1,3)$ 到碎片 $5(2,4)$ 最短耗时： $2$；
碎片 $5(2,4)$ 到碎片 $6(3,3)$ 最短耗时： $6$（碎片 $5$ 到 碎片 $6$ 之间有障碍物需要绕路：$(2,4)->(1,4)->(1,3)->(1,2)->(2,2)->(3,2)->(3,3)$）
碎片 $6(3,3)$ 到宝箱 $(4,4)$ 最短耗时： $2$
总计耗时：$3+2+3+5=13$

题解

思路

BFS + dp实现

1. 根据地图确定出起点、终点和各等级碎片坐标。这些坐标可认定为特殊坐标。
2. 对给定碎片坐标进行编号，按照起点，等级碎片(先编低等级碎片)，盒子顺序进行编号。
3. 使用BFS计算各个特殊坐标之间的最短距离。
4. 使用状态dp确定最短耗时，其中dp[i]代表以当前编号收尾 收集本等级所有碎片之后 + 低等级碎片的最小代价
5. 状态转移过程为：
   1. 起点可以上一轮所有可能终点，本等级收集所有碎片的可行路径(可用全排列枚举)
   2. 按照1的枚举所有情况更新dp[ 终点 ]的值
6. 按照5处理完起点和所有碎片的最短耗时之后，枚举所有最高碎片到盒子的情况，碎片i 对应时间为dp[i] + dist[i][boxIndex]， 其中最小值就是结果。

C++

#include<bits/stdc++.h>
using namespace std;

int n, m;
vector<vector<int>> grid;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};



// 从一个点出发，求到所有格子的最短距离
vector<vector<int>> bfs(pair<int, int> start) {
    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int, int>> q;

    dist[start.first][start.second] = 0;
    q.push(start);

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();

        int x = cur.first;
        int y = cur.second;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                // 只有障碍物 1 不能通过
                if (grid[nx][ny] != 1 && dist[nx][ny] == -1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }

    return dist;
}

int getMinTime() {
    // 起点和宝箱的坐标
    pair<int, int> start, box;
    // 分类存储碎片位置
    vector<vector<pair<int,int>>> group(10);
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 2) {
                start = {i, j};
            } else if (grid[i][j] == 3) {
                box = {i, j};
            } else if (grid[i][j] >= 4 && grid[i][j] <= 9) {
                group[grid[i][j]].push_back({i, j});
            }
        }
    }
    
    // 关键点位
    vector<pair<int,int>> points;
    points.push_back(start);
    
    vector<vector<int>> groups(10);
    
    // 给碎片编号
    for (int i = 4; i <= 9; i++) {
        for (auto p : group[i]) {
           groups[i].push_back(points.size());
            points.push_back(p);
        }
    }
    
    int boxIds = points.size();
    points.push_back(box);
    
    int k = points.size();
    // 计算不同点出发到其它点的最小距离， 其中-1表示不可达
    vector<vector<int>> dist(k, vector<int>(k, -1));
    
    // 使用bfs计算点之间最短距离
    for (int i = 0; i < k; i++) {
         vector<vector<int>> d = bfs(points[i]);
         for (int j = 0; j < k; j++) {
             int x = points[j].first;
             int y = points[j].second;
             dist[i][j] = d[x][y];
         }
    }
    // dp[位置编号] = 以当前编号收尾 收集本等级所有碎片 + 低等级碎片的最小代价
    map<int, int> dp;
    dp[0] = 0;
    // 上一轮所有终点
    vector<int> last;
    last.push_back(0);
    for (int i = 4; i <= 9; i++) {
        if (groups[i].empty()) {
            continue;
        }
        vector<int> next;
        vector<int> order = groups[i];
        next = order;
        sort(order.begin(), order.end());
        // 全排列枚举当前等级碎片收集顺序
        do {
            for (auto& lastPos : last) {
                
                if (!dp.count(lastPos)) continue;
                int curCost = dp[lastPos];
                int pre = lastPos;
                
                bool valid = true;
                for (int node : order) {
                    // 不可达
                    if (dist[pre][node] == -1) {
                        valid = false;
                        break;
                    }
                    curCost += dist[pre][node];
                    pre = node;
                }
                //此路径不合法
                if (!valid) {
                    continue;
                }
                if (!dp.count(pre) || curCost < dp[pre]) {
                    dp[pre] = curCost;
                }
            }
        } while (next_permutation(order.begin(), order.end()));
        last = next;
    }
    
    int ans = INT_MAX;
    for (auto lastPos : last) {
        if (!dp.count(lastPos) || dist[lastPos][boxIds] == -1) {
            continue;
        }
        ans = min(ans, dp[lastPos] + dist[lastPos][boxIds]);
    }
    
    return ans;
    
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    grid.assign(n, vector<int>(m));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    cout << getMinTime() << endl;
    return 0;
}

java

import java.util.*;
import java.io.*;

public class Main {

    static int n, m;
    static int[][] grid;

    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    static class Node {
        int x, y;
        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    // 从一个点出发，求到所有格子的最短距离
    static int[][] bfs(Node start) {

        int[][] dist = new int[n][m];
        for (int[] row : dist) Arrays.fill(row, -1);

        Queue<Node> q = new LinkedList<>();

        dist[start.x][start.y] = 0;
        q.offer(start);

        while (!q.isEmpty()) {

            Node cur = q.poll();

            int x = cur.x;
            int y = cur.y;

            for (int i = 0; i < 4; i++) {

                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {

                    // 只有障碍物 1 不能通过
                    if (grid[nx][ny] != 1 && dist[nx][ny] == -1) {

                        dist[nx][ny] = dist[x][y] + 1;
                        q.offer(new Node(nx, ny));
                    }
                }
            }
        }

        return dist;
    }

    static int getMinTime() {

        // 起点和宝箱的坐标
        Node start = null, box = null;

        // 分类存储碎片位置
        List<List<Node>> group = new ArrayList<>();
        for (int i = 0; i <= 9; i++) group.add(new ArrayList<>());

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {

                if (grid[i][j] == 2) {
                    start = new Node(i, j);

                } else if (grid[i][j] == 3) {
                    box = new Node(i, j);

                } else if (grid[i][j] >= 4 && grid[i][j] <= 9) {
                    group.get(grid[i][j]).add(new Node(i, j));
                }
            }
        }

        // 关键点位（所有起点 + 碎片 + 宝箱）
        List<Node> points = new ArrayList<>();
        points.add(start);

        List<List<Integer>> groups = new ArrayList<>();
        for (int i = 0; i <= 9; i++) groups.add(new ArrayList<>());

        // 给碎片编号
        for (int i = 4; i <= 9; i++) {
            for (Node p : group.get(i)) {
                groups.get(i).add(points.size());
                points.add(p);
            }
        }

        int boxId = points.size();
        points.add(box);

        int k = points.size();

        // 计算不同点出发到其它点的最小距离，-1表示不可达
        int[][] dist = new int[k][k];

        for (int i = 0; i < k; i++) {

            int[][] d = bfs(points.get(i));

            for (int j = 0; j < k; j++) {
                Node p = points.get(j);
                dist[i][j] = d[p.x][p.y];
            }
        }

        // dp[位置编号] = 当前收集状态的最小代价
        Map<Integer, Integer> dp = new HashMap<>();
        dp.put(0, 0);

        // 上一轮所有终点
        List<Integer> last = new ArrayList<>();
        last.add(0);

        for (int i = 4; i <= 9; i++) {

            if (groups.get(i).isEmpty()) continue;

            List<Integer> order = new ArrayList<>(groups.get(i));
            List<Integer> next = new ArrayList<>(order);

            Collections.sort(order);

            do {

                for (int lastPos : last) {

                    if (!dp.containsKey(lastPos)) continue;

                    int curCost = dp.get(lastPos);
                    int pre = lastPos;

                    boolean valid = true;

                    for (int node : order) {

                        // 不可达
                        if (dist[pre][node] == -1) {
                            valid = false;
                            break;
                        }

                        curCost += dist[pre][node];
                        pre = node;
                    }

                    // 此路径不合法
                    if (!valid) continue;

                    if (!dp.containsKey(pre) || curCost < dp.get(pre)) {
                        dp.put(pre, curCost);
                    }
                }

            } while (nextPermutation(order));

            last = next;
        }

        int ans = Integer.MAX_VALUE;

        for (int lastPos : last) {

            if (!dp.containsKey(lastPos) || dist[lastPos][boxId] == -1)
                continue;

            ans = Math.min(ans, dp.get(lastPos) + dist[lastPos][boxId]);
        }

        return ans;
    }

    // 全枚举
    static boolean nextPermutation(List<Integer> a) {

        int i = a.size() - 2;

        while (i >= 0 && a.get(i) >= a.get(i + 1)) i--;
        if (i < 0) return false;

        int j = a.size() - 1;

        while (a.get(j) <= a.get(i)) j--;

        Collections.swap(a, i, j);

        Collections.reverse(a.subList(i + 1, a.size()));

        return true;
    }

    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        grid = new int[n][m];

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                grid[i][j] = sc.nextInt();

        System.out.println(getMinTime());
    }
}

python

import sys
from collections import deque
from itertools import permutations

n, m = map(int, sys.stdin.readline().split())
grid = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# 从一个点出发，求到所有格子的最短距离
def bfs(start):

    dist = [[-1] * m for _ in range(n)]
    q = deque()

    dist[start[0]][start[1]] = 0
    q.append(start)

    while q:

        x, y = q.popleft()

        for i in range(4):

            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m:

                # 只有障碍物 1 不能通过
                if grid[nx][ny] != 1 and dist[nx][ny] == -1:

                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))

    return dist


def solve():

    # 起点和宝箱的坐标
    start = box = None

    # 分类存储碎片位置
    group = {i: [] for i in range(10)}

    for i in range(n):
        for j in range(m):

            if grid[i][j] == 2:
                start = (i, j)

            elif grid[i][j] == 3:
                box = (i, j)

            elif 4 <= grid[i][j] <= 9:
                group[grid[i][j]].append((i, j))

    # 关键点位
    points = [start]
    groups = {i: [] for i in range(10)}

    # 给碎片编号
    for i in range(4, 10):
        for p in group[i]:
            groups[i].append(len(points))
            points.append(p)

    box_id = len(points)
    points.append(box)

    k = len(points)

    # dist[i][j] = i点到j点最短路（-1不可达）
    dist = [[0] * k for _ in range(k)]

    for i in range(k):
        d = bfs(points[i])

        for j in range(k):
            x, y = points[j]
            dist[i][j] = d[x][y]

    # dp[位置编号] = 当前收集状态最小代价
    dp = {0: 0}

    # 上一轮所有终点
    last = [0]

    for i in range(4, 10):

        if not groups[i]:
            continue

        order = groups[i]

        next_last = set()

        for perm in set(permutations(order)):

            for last_pos in last:

                if last_pos not in dp:
                    continue

                cur = dp[last_pos]
                pre = last_pos

                valid = True

                for node in perm:

                    # 不可达
                    if dist[pre][node] == -1:
                        valid = False
                        break

                    cur += dist[pre][node]
                    pre = node

                # 此路径不合法
                if not valid:
                    continue

                if pre not in dp or cur < dp[pre]:
                    dp[pre] = cur
                    next_last.add(pre)

        last = list(next_last)

    ans = float('inf')

    for last_pos in last:

        if last_pos not in dp:
            continue

        if dist[last_pos][box_id] == -1:
            continue

        ans = min(ans, dp[last_pos] + dist[last_pos][box_id])

    print(ans)


solve()

javascript

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let input = [];
rl.on("line", line => {
    input.push(line.trim());
});

rl.on("close", () => {

    let idx = 0;

    let [n, m] = input[idx++].split(" ").map(Number);

    let grid = [];

    for (let i = 0; i < n; i++) {
        grid.push(input[idx++].split(" ").map(Number));
    }

    const dx = [1, -1, 0, 0];
    const dy = [0, 0, 1, -1];

    // BFS：从一个点出发求最短路
    function bfs(start) {

        let dist = Array.from({ length: n }, () => Array(m).fill(-1));
        let q = [];

        dist[start[0]][start[1]] = 0;
        q.push(start);

        while (q.length) {

            let [x, y] = q.shift();

            for (let i = 0; i < 4; i++) {

                let nx = x + dx[i];
                let ny = y + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {

                    if (grid[nx][ny] !== 1 && dist[nx][ny] === -1) {

                        dist[nx][ny] = dist[x][y] + 1;
                        q.push([nx, ny]);
                    }
                }
            }
        }

        return dist;
    }

    let start, box;
    let group = Array.from({ length: 10 }, () => []);

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {

            if (grid[i][j] === 2) start = [i, j];
            else if (grid[i][j] === 3) box = [i, j];
            else if (grid[i][j] >= 4 && grid[i][j] <= 9) {
                group[grid[i][j]].push([i, j]);
            }
        }
    }

    let points = [start];
    let groups = Array.from({ length: 10 }, () => []);

    for (let i = 4; i <= 9; i++) {
        for (let p of group[i]) {
            groups[i].push(points.length);
            points.push(p);
        }
    }

    let boxId = points.length;
    points.push(box);

    let k = points.length;

    let dist = Array.from({ length: k }, () => Array(k).fill(0));

    for (let i = 0; i < k; i++) {

        let d = bfs(points[i]);

        for (let j = 0; j < k; j++) {
            dist[i][j] = d[points[j][0]][points[j][1]];
        }
    }

    let dp = new Map();
    dp.set(0, 0);

    let last = [0];
    
    // 全枚举
    function nextPermutation(a) {

        let i = a.length - 2;

        while (i >= 0 && a[i] >= a[i + 1]) i--;
        if (i < 0) return false;

        let j = a.length - 1;
        while (a[j] <= a[i]) j--;

        [a[i], a[j]] = [a[j], a[i]];

        let l = i + 1, r = a.length - 1;
        while (l < r) {
            [a[l], a[r]] = [a[r], a[l]];
            l++; r--;
        }

        return true;
    }

    for (let i = 4; i <= 9; i++) {

        if (!groups[i].length) continue;

        let order = [...groups[i]].sort((a, b) => a - b);

        let nextLast = [];

        do {

            for (let lastPos of last) {

                if (!dp.has(lastPos)) continue;

                let cur = dp.get(lastPos);
                let pre = lastPos;

                let ok = true;

                for (let node of order) {

                    if (dist[pre][node] === -1) {
                        ok = false;
                        break;
                    }

                    cur += dist[pre][node];
                    pre = node;
                }

                if (!ok) continue;

                if (!dp.has(pre) || cur < dp.get(pre)) {
                    dp.set(pre, cur);
                    nextLast.push(pre);
                }
            }

        } while (nextPermutation(order));

        last = nextLast;
    }

    let ans = Infinity;

    for (let pos of last) {

        if (dist[pos][boxId] === -1) continue;

        ans = Math.min(ans, dp.get(pos) + dist[pos][boxId]);
    }

    console.log(ans);
});

Go

package main

import (
	"fmt"
	"sort"
)

var n, m int
var grid [][]int

var dx = []int{1, -1, 0, 0}
var dy = []int{0, 0, 1, -1}

type Node struct {
	x, y int
}

// 从一个点出发，求到所有格子的最短距离
func bfs(start Node) [][]int {

	dist := make([][]int, n)
	for i := range dist {
		dist[i] = make([]int, m)
		for j := range dist[i] {
			dist[i][j] = -1
		}
	}

	q := []Node{start}
	dist[start.x][start.y] = 0

	for len(q) > 0 {

		cur := q[0]
		q = q[1:]

		for i := 0; i < 4; i++ {

			nx := cur.x + dx[i]
			ny := cur.y + dy[i]

			if nx >= 0 && nx < n && ny >= 0 && ny < m {

				// 只有障碍物 1 不能通过
				if grid[nx][ny] != 1 && dist[nx][ny] == -1 {

					dist[nx][ny] = dist[cur.x][cur.y] + 1
					q = append(q, Node{nx, ny})
				}
			}
		}
	}

	return dist
}


func nextPermutation(a []int) bool {

	i := len(a) - 2
	for i >= 0 && a[i] >= a[i+1] {
		i--
	}
	if i < 0 {
		return false
	}

	j := len(a) - 1
	for a[j] <= a[i] {
		j--
	}

	a[i], a[j] = a[j], a[i]

	for l, r := i+1, len(a)-1; l < r; l, r = l+1, r-1 {
		a[l], a[r] = a[r], a[l]
	}

	return true
}

func main() {

	fmt.Scan(&n, &m)

	grid = make([][]int, n)
	for i := 0; i < n; i++ {
		grid[i] = make([]int, m)
		for j := 0; j < m; j++ {
			fmt.Scan(&grid[i][j])
		}
	}

	// 起点和宝箱
	var start, box Node

	// group[i] 存 i号碎片所有坐标
	group := make([][]Node, 10)

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {

			if grid[i][j] == 2 {
				start = Node{i, j}
			} else if grid[i][j] == 3 {
				box = Node{i, j}
			} else if grid[i][j] >= 4 && grid[i][j] <= 9 {
				group[grid[i][j]] = append(group[grid[i][j]], Node{i, j})
			}
		}
	}

	points := []Node{start}

	// groups[i] 存碎片在points中的编号
	groups := make([][]int, 10)

	for i := 4; i <= 9; i++ {
		for _, p := range group[i] {
			groups[i] = append(groups[i], len(points))
			points = append(points, p)
		}
	}

	boxID := len(points)
	points = append(points, box)

	k := len(points)

	// dist[i][j] = i到j最短路
	dist := make([][]int, k)
	for i := range dist {
		dist[i] = make([]int, k)
	}

	for i := 0; i < k; i++ {

		d := bfs(points[i])

		for j := 0; j < k; j++ {
			dist[i][j] = d[points[j].x][points[j].y]
		}
	}

	// dp
	dp := map[int]int{0: 0}
	last := []int{0}

	// 每一组碎片依次处理
	for i := 4; i <= 9; i++ {

		if len(groups[i]) == 0 {
			continue
		}

		order := append([]int{}, groups[i]...)
		sort.Ints(order)

		nextLast := []int{}

		for {

			for _, lastPos := range last {

				cur, ok := dp[lastPos]
				if !ok {
					continue
				}

				pre := lastPos
				sum := cur
				valid := true

				for _, node := range order {

					if dist[pre][node] == -1 {
						valid = false
						break
					}

					sum += dist[pre][node]
					pre = node
				}

				if !valid {
					continue
				}

				if v, ok := dp[pre]; !ok || sum < v {
					dp[pre] = sum
					nextLast = append(nextLast, pre)
				}
			}

			if !nextPermutation(order) {
				break
			}
		}

		last = nextLast
	}

	ans := int(^uint(0) >> 1)

	for _, pos := range last {

		if dist[pos][boxID] == -1 {
			continue
		}

		ans = min(ans, dp[pos]+dist[pos][boxID])
	}

	fmt.Println(ans)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}