2018校招真题 拼多多 迷宫寻路

题目链接

因为在准备谷歌面试中,本来准备最近并不更新刷过的题,多刷些题。但由于这题对我来说意义很大,所以记载了下来。

为了节省些时间,题目题意在这里不复制粘贴了,可以在上面的链接跳转过去。

Solution

Idea

题目是很直接的 BFS , 相比较最简单的迷宫寻路问题,这题增加了钥匙和门,即如果我们想要通过一个门,必须在此之前获得它的钥匙。 注意题目中的数据范围,门和钥匙最多为 10. 故可以用状态压缩记录状态。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;

typedef struct point
{
int x, y, key, step;
point() {}
point(int _x, int _y, int _key, int _step) : x(_x), y(_y), key(_key), step(_step) { }
} P;

int n, m;
char maze[107][107];
bool vis[107][107][1050];
const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};

int main()
{
memset(vis, false, sizeof(vis));
scanf("%d%d", &n, &m);
getchar();
char ch;
int startX, startY;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
ch = getchar();
maze[i][j] = ch;
if(ch == '2')
{
startX = i;
startY = j;
}
}
getchar();
}

queue<P> que;
que.push(P(startX, startY, 0, 0));
int curX, curY;
P p;

while(!que.empty())
{
p = que.front();
que.pop();
if(maze[p.x][p.y] == '3')
{
printf("%d\n", p.step);
break;
}

for(int i=0; i<4; i++)
{
curX = p.x + dx[i];
curY = p.y + dy[i];
if(curX < 0 || curX>=n || curY < 0 || curY >= m || maze[curX][curY] == '0' || vis[curX][curY][p.key])
continue;
ch = maze[curX][curY];
if(ch >= 'A' && ch <= 'Z')
{
if( p.key & (1 << (ch-'A') ) )
{
que.push(P(curX, curY, p.key, p.step+1));
vis[curX][curY][p.key] = true;
}
}
else if(ch >= 'a' && ch <= 'z')
{
que.push( P(curX, curY, p.key | ( 1 << (ch-'a') ), p.step+1) );
vis[curX][curY][p.key] = true;
}
else
{
que.push(P(curX, curY, p.key, p.step+1));
vis[curX][curY][p.key] = true;
}
}

}
return 0;
}

闲言

之所以说这题对我意义比较大,是因为在一次很久之前的训练时,有学长出了这道题。

那时候我还是个小白,几乎啥都不会,连 dp 是什么都不知道。那时候做到这个题还是蛮受打击的。讲题目时这题是邓新议(应该是)学长讲的。学长又讲到状压,把拿到我钥匙压缩为一个状态,当时我的心里几乎是崩溃的,因为学长们说的名词我都没有听过, 有一种很无力的感觉。

回去的时候,我一个人走在北操前的路上,有些流泪?因为深深地感受到了自己什么都不知道。于是回去查了 dp,状态压缩一些名词的意思, 这才知道原来 dp 是动态规划的意思。

所以对这题印象蛮深的,过去后一直想再见见这题。昨天刷题时看到题目名字中有个迷宫寻路,心想,不会是有钥匙和门的那道吧。

现在在看这道题,只感觉是一道很基础的题目了,很容易地就能够过掉。对比起来,自己还是学到了些知识的,进步了很多。 也算是给那晚独自一人的自己一个回答吧。

❤采之欲遗谁,所思在远道。❤
0%