[LeetCode][BFS] 317. Shortest Distance from All Buildings

Problem

More LeetCode Discussions
You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

Each 0 marks an empty land which you can pass by freely.
Each 1 marks a building which you cannot pass through.
Each 2 marks an obstacle which you cannot pass through.
For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

1 - 0 - 2 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.

Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

Solution

找出所有的1腌零,然后依次對(duì)他們BFS,然后得到一張dis的表格摩桶,canReach用來(lái)追蹤有多少個(gè)1可以到達(dá)這個(gè)點(diǎn),只有canReach[i][j] == points.size()說(shuō)明所有的1都可以到達(dá)恬惯。

struct QType {
  pair<int, int> p;
  int step;
};

class Solution {
private:
    vector<vector<int>> canReach;
    vector<vector<int>> dis;
    vector<pair<int, int>> points;
    vector<vector<bool>> canUse;
    int steps[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public:
    void bfs(vector<vector<int>> &grid, pair<int, int> p) {
        queue<QType> q;
        QType node;
        node.p = p;
        node.step = 0;
        for(int i = 0; i < canUse.size(); i++) {
            for(int j = 0; j < canUse[i].size(); j++) {
                canUse[i][j] = true;
            }
        }
        canUse[p.first][p.second] = false;
        q.push(node);
        
        while (!q.empty()) {
            QType node = q.front();
            q.pop();
            for(int i = 0; i < 4; i++) {
                int newX = node.p.first + steps[i][0];
                int newY = node.p.second + steps[i][1];
                int step = node.step + 1;
                if (0 <= newX && newX < canUse.size() && 0 <= newY && newY < canUse[0].size() && canUse[newX][newY] && 
                grid[newX][newY] == 0) {
                    QType node;
                    pair<int, int> p;
                    p.first = newX;
                    p.second = newY;
                    node.p = p;
                    node.step = step;
                    q.push(node);
                    canUse[newX][newY] = false;
                    dis[newX][newY] += step;
                    canReach[newX][newY]++;
                }
            }
        }
    }
    
    int shortestDistance(vector<vector<int>>& grid) {
        if (grid.size() == 0 || grid[0].size() == 0) {
            return -1;
        }
        
        canReach.resize(grid.size());
        dis.resize(grid.size());
        canUse.resize(grid.size());
        
        for(int i = 0; i < dis.size(); i++) {
            canReach[i].resize(grid[0].size());
            dis[i].resize(grid[0].size());
            canUse[i].resize(grid[0].size());
        }
        
        for(int i = 0; i < dis.size(); i++) {
            for(int j = 0; j < dis[i].size(); j++) {
                dis[i][j] = canReach[i][j] = 0;
            }
        }
        
        for(int i = 0; i < grid.size(); i++) {
            for(int j = 0; j < grid[i].size(); j++) {
                if (grid[i][j] == 1) {
                    pair<int, int> p;
                    p.first = i;
                    p.second = j;
                    points.push_back(p);
                }
            }
        }
        
        for(int i = 0; i < points.size(); i++) {
            bfs(grid, points[i]);
        }
        
        int minDist = -1;
        for(int i = 0; i < canReach.size(); i++) {
            for(int j = 0; j < canReach[i].size(); j++) {
                if (canReach[i][j] == points.size()) {
                    if (minDist == -1) {
                        minDist = dis[i][j];
                    } else {
                        minDist = min(minDist, dis[i][j]);
                    }
                }
            }
        }
        
        return minDist;
    }
};
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末滞伟,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子狠毯,更是在濱河造成了極大的恐慌藐握,老刑警劉巖靴拱,帶你破解...
    沈念sama閱讀 217,277評(píng)論 6 503
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異猾普,居然都是意外死亡袜炕,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,689評(píng)論 3 393
  • 文/潘曉璐 我一進(jìn)店門初家,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)偎窘,“玉大人,你說(shuō)我怎么就攤上這事溜在∧爸” “怎么了?”我有些...
    開封第一講書人閱讀 163,624評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵掖肋,是天一觀的道長(zhǎng)仆葡。 經(jīng)常有香客問(wèn)我,道長(zhǎng)培遵,這世上最難降的妖魔是什么浙芙? 我笑而不...
    開封第一講書人閱讀 58,356評(píng)論 1 293
  • 正文 為了忘掉前任,我火速辦了婚禮籽腕,結(jié)果婚禮上嗡呼,老公的妹妹穿的比我還像新娘。我一直安慰自己皇耗,他們只是感情好南窗,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,402評(píng)論 6 392
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著郎楼,像睡著了一般万伤。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上呜袁,一...
    開封第一講書人閱讀 51,292評(píng)論 1 301
  • 那天敌买,我揣著相機(jī)與錄音,去河邊找鬼阶界。 笑死虹钮,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的膘融。 我是一名探鬼主播芙粱,決...
    沈念sama閱讀 40,135評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼氧映!你這毒婦竟也來(lái)了春畔?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 38,992評(píng)論 0 275
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤岛都,失蹤者是張志新(化名)和其女友劉穎律姨,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體疗绣,經(jīng)...
    沈念sama閱讀 45,429評(píng)論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡线召,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,636評(píng)論 3 334
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了多矮。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片缓淹。...
    茶點(diǎn)故事閱讀 39,785評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖塔逃,靈堂內(nèi)的尸體忽然破棺而出讯壶,到底是詐尸還是另有隱情,我是刑警寧澤湾盗,帶...
    沈念sama閱讀 35,492評(píng)論 5 345
  • 正文 年R本政府宣布伏蚊,位于F島的核電站,受9級(jí)特大地震影響格粪,放射性物質(zhì)發(fā)生泄漏躏吊。R本人自食惡果不足惜氛改,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,092評(píng)論 3 328
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望比伏。 院中可真熱鬧胜卤,春花似錦、人聲如沸赁项。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,723評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)悠菜。三九已至舰攒,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間悔醋,已是汗流浹背摩窃。 一陣腳步聲響...
    開封第一講書人閱讀 32,858評(píng)論 1 269
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留芬骄,地道東北人偶芍。 一個(gè)月前我還...
    沈念sama閱讀 47,891評(píng)論 2 370
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像德玫,于是被迫代替她去往敵國(guó)和親匪蟀。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,713評(píng)論 2 354

推薦閱讀更多精彩內(nèi)容