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

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

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

Solution

Idea

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

Code

#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 是动态规划的意思。

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

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