`

Google Interview - 警察到房间的最短距离

 
阅读更多

一个 n x n 矩阵,每个房间可能是封闭的房间,可能是警察,可能是开的房间, 封闭的房间不能过,返回一个n x n矩阵,每一个元素是最近的警察到这个房间的最短距离。 初始矩阵中-1代表封闭房间,INT_MAX代表普通房间,0代表有警察的房间。

 

Solution: 把警察都找出来,然后一起push到BFS的queue里面,同时搜索。复杂度可降为O(n^2)。

Starting from police and override the distance with smaller value if multiple polices can reach the same office. 

void police_and_rooms(vector<vector<int>>& rooms) {
    int n = (int)rooms.size();
    if (n == 0) return;
    
    set<pair<int,int>> visited;
    queue<pair<int,int>> q;
    queue<int> dists;
    
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            if (rooms[i][j] == 0) {
                q.push({i,j});
                visited.insert({i,j});
                dists.push(0);
            }
        }
    }
    while(!q.empty()) {
        auto pos = q.front();
        q.pop();
        
        auto dist = dists.front();
        dists.pop();
        
        vector<pair<int,int>> dirs =  {{0,1}, {0,-1}, {1,0}, {-1,0}};
        for(auto dir : dirs) {
            pair<int,int> cur = {dir.first + pos.first, dir.second + pos.second};
            if(cur.first < 0 || cur.second < 0 || cur.first >= n || cur.second >= n)
                continue;
            
            if(visited.count(cur)) continue;
            if(rooms[cur.first][cur.second] == -1) {
                visited.insert(cur);
                continue;
            }
            
            visited.insert(cur);
            
            dists.push(dist + 1);
            q.push(cur);
            
            rooms[cur.first][cur.second] =
            min(rooms[cur.first][cur.second], dist + 1);
        }
    }
}

 

Reference:

http://www.mitbbs.com/article_t/JobHunting/32767115.html

http://www.fgdsb.com/2015/01/03/police-and-rooms/

分享到:
评论

相关推荐

    vue-interview-questions-master.zip

    VUE 面试题汇合 vue-interview-questions-master VUE 面试题汇合 vue-interview-questions-master VUE 面试题汇合 vue-interview-questions-master VUE 面试题汇合 vue-interview-questions-master VUE 面试题...

    interview-docs-master.zip

    【标题】"interview-docs-master.zip" 是一个压缩文件,通常包含一系列关于面试准备的文档,特别是针对Java程序员的面试资源。这个压缩包可能是为了帮助求职者在寻找Java开发职位时,熟悉并掌握常见的面试问题和解答...

    123-Essential-JavaScript-Interview-Question, JavaScript访问问题.zip

    123-Essential-JavaScript-Interview-Question, JavaScript访问问题 123 -JavaScript-Interview-Questions这本书将由 2018年06月 完成并可以供购买。 如果你想让我把这本书的早期拷贝,请在这里添加你的NAME 和电子...

    Algorithm-coding-interview-university.zip

    此外,还会涉及图算法,如深度优先搜索(DFS)和广度优先搜索(BFS),以及Dijkstra算法和Floyd-Warshall算法等用于计算最短路径的方法。这些算法在路由、社交网络分析等领域有着广泛的应用。 在实际的编码面试中,...

    Interview-code-practice-python-master_escapek5u_python_

    标题中的"Interview-code-practice-python-master_escapek5u_python_"暗示了这是一个关于Python编程的面试题练习项目,可能包含了各种常见的编程题目,旨在帮助开发者准备技术面试。"escapek5u"可能是创建或整理这个...

    Interview-Materials.rar__interview_interview-q

    这份名为"Interview-Materials.rar__interview_interview-q"的压缩包文件显然是为准备IT行业面试者精心准备的一份资源集合。它涵盖了C、C++以及Linux等多个关键领域的知识,帮助求职者一站式获取必要的面试准备材料...

    Algorithm_for_Interview-Chinese-master.zip

    "Algorithm_for_Interview-Chinese-master.zip" 这个压缩包文件很可能包含了丰富的面试准备资料,聚焦于C++语言,涵盖了多种核心算法和概念。让我们深入探讨一下这些关键知识点。 1. **查找与排序**: - **查找...

    Java-Interview-超全集合github上评分最高的jiva面试题

    "Java-Interview-超全集合github上评分最高的jiva面试题"就是一个这样的宝藏,它涵盖了Java编程语言、Git版本控制工具以及面试策略等多个方面的知识点。以下是这些内容的详细解析: 1. **Java基础** - **数据类型...

    Technical-Interview-Preparation-Checklist.pdf

    Technical-Interview-Preparation-Checklist.pdf

    juejin-interview-软考-网络工程师资源

    juejin-interview-软考-网络工程师资源

    web-interview-软考-网络工程师资源

    web-interview-软考-网络工程师资源

Global site tag (gtag.js) - Google Analytics