求一道题思路

在一个迷宫中，给定起点终点，
迷宫中1代表礼物，2代表墙，3代表空地
要求输出收集完所有礼物以后走到终点的最短路径。如果不可能收集完则输出-1

先数一下有几个礼物，dfs应该可以吧？就是复杂度有点高…可是bfs走重复的点，好像要更新礼物数…不知道怎么弄

会两种方法
假设迷宫大小n*m 有k个礼物
第一种复杂度为k! + (nm)^2
做法：
(1)求出任意一对点之间最短路的长度，这可以通过nm次BFS做到
(2)枚举k个礼物经过的顺序，共k!种，相邻两个礼物之间用(1)求得得最短路连接起来

第二种复杂度为nm*2^k
做法
用dis[x][y][S]表示从起点到点(x, y)，而且必须已经经过S里面的礼物（S是一个集合）
这样答案就是dis[终点][全集]
具体写代码的时候S可以用一个int表示，用一些位运算的技巧

1. 第二种算法伪代码
   
2. 
   
3. Q.push(sx); Q.push(sy); Q.push(0); //太懒了，Q是一个队列，一次压3个弹3个
   
4. while (Q.empty() == false){
   
5.   int nowx = Q.front(); Q.pop(); int nowy = Q.front(); Q.pop(); int nowS = Q.front(); Q.pop();
   
6.   for (int d = 0; d < 4; d++){ //上下左右
   
7.     int newx = nowx + dx[d], newy = nowy + dy[d]; //const int dx[4] = {0, 0, 1, -1}; const int dy[4] = {1, -1, 0, 0};
   
8.     if (newx, newy 超过边界或者是障碍)
   
9.       continue;
   
10.     //我们假设每个格子有一个0..k-1的label，用l[x][y]表示。可以自己设置一个。没有礼物的地方l[x][y] = -1;
    
11.     int newS = nowS; //设置为之前经过的

复制代码

不知道为啥老吞代码 LZ先意会一下 不懂再问我吧

最近面的一个startup中的oa题！当时只写了一个greedy／nearest neighbor的解法（并且还有bug），现在想到应该是tsp，但是tsp的解法略复杂，面试的时间短暂，能写完整的实在太挑战了。

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

补充内容 (2019-2-21 06:03):

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

步惊云 发表于 2019-2-21 04:58
弟弟, 我找不到movie, 是什么名字?

我打错年份了，难怪你找不到