iT邦幫忙

2026 iThome 鐵人賽

DAY 20
0
Software Development

30天刷完leetcoode75系列 第 20 篇

C++ 演算法練習 Day20|1926, 374 題解與思路分享

  • 分享至 

  • xImage
  •  

https://ithelp.ithome.com.tw/upload/images/20261004/20184265AOIQ2c3wCf.png

題目解析:給定一個迷宮矩陣,找出從起點走到最近出口(邊界的空地)最少需要走幾步,起點本身不能算作出口
解題思路:找最短路徑直接用 BFS,因為它一層層往外找,最先遇到的出口保證是最佳解。先設 dy 跟 dx 陣列輔助上下左右移動,再設一個佇列裝目前的位子,並把起點標記成牆壁 '+' 防止回頭。丟進迴圈跑,每次把同一層的位子拿出來往四方拓展。如果超出界線或撞牆就跳過,走到邊界就回傳累積步數,不然就把新位子標成牆並塞進佇列。全跑完沒找到就回傳 -1

class Solution {
public:
    int nearestExit(vector>& maze, vector& entrance) {
        int m = maze.size(), n = maze[0].size();
        int dy[4] = {1, -1, 0, 0};
        int dx[4] = {0, 0, 1, -1};

        queue> q;
        q.push({entrance[0], entrance[1]});
        maze[entrance[0]][entrance[1]] = '+';

        int steps = 0;
        while (!q.empty()) {
            int sz = q.size();
            steps++;
            while (sz--) {
                auto [y, x] = q.front(); q.pop();
                for (int d = 0; d < 4; d++) {
                    int ny = y + dy[d], nx = x + dx[d];
                    if (ny < 0 || ny >= m || nx < 0 || nx >= n) continue;
                    if (maze[ny][nx] == '+') continue;
                    if (ny == 0 || ny == m - 1 || nx == 0 || nx == n - 1)
                        return steps;
                    maze[ny][nx] = '+';
                    q.push({ny, nx});
                }
            }
        }
        return -1;
    }
};

https://ithelp.ithome.com.tw/upload/images/20261004/201842657dQZQMuyyW.png

題目解析:經典猜數字遊戲,在 1 到 n 之間猜出系統設定的數字,可呼叫 API 知道猜的數字是太大、太小還是剛好猜中
解題思路:為了快速鎖定答案,直接使用二分搜尋法。設變數 ans 裝答案,並寫一個遞迴函數。為了避免相加時超過整數上限導致溢位,中間值刻意寫成 l + (r - l) / 2。每次取中間數字呼叫 API:回傳 0 代表猜中,把答案給 ans 並結束;回傳 -1 代表猜太大,把範圍縮到左半邊繼續找;回傳 1 就往右半邊找。最後回傳 ans


上一篇
C++ 演算法練習 Day19|471, 17 題解與思路分享
下一篇
C++ 演算法練習 Day21|215, 216 題解與思路分享
系列文
30天刷完leetcoode75 共 22 篇
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言