基因序列可以表示為一條由 8 個字符組成的字符串，其中每個字符都是 'A'、'C'、'G' 和 'T' 之一。

假設我們需要調查從基因序列 start 變為 end 所發生的基因變化。一次基因變化就意味著這個基因序列中的一個字符發生了變化。

• 例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因變化。

另有一個基因庫 bank 記錄了所有有效的基因變化，只有基因庫中的基因才是有效的基因序列。（變化后的基因必須位于基因庫 bank 中）

給你兩個基因序列 start 和 end ，以及一個基因庫 bank ，請你找出并返回能夠使 start 變化為 end 所需的最少變化次數。如果無法完成此基因變化，返回 -1 。

注意：起始基因序列 start 默認是有效的，但是它并不一定會出現在基因庫中。

示例 1：

輸入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
輸出：1

示例 2：

輸入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
輸出：2

示例 3：

輸入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
輸出：3

提示：

• start.length == 8
• end.length == 8
• 0 <= bank.length <= 10
• bank[i].length == 8
• start、end 和 bank[i] 僅由字符 ['A', 'C', 'G', 'T'] 組成

int minMutation(string startGene, string endGene, vector<string>& bank) {if (startGene == endGene) {return 0;}unordered_set<string> vis;unordered_set<string> hash(bank.begin(), bank.end());const string change = "ACGT";queue<string> que;que.push(startGene);hash.insert(startGene);int step = 0;while (!que.empty()) {step++;int n = que.size();while (n--) {string str = que.front();que.pop();for (int i = 0; i < 8; ++i) {string tmp = str;for (int j = 0; j < 4; ++j) {tmp[i] = change[j];if (hash.count(tmp) && !vis.count(tmp)) {if (tmp == endGene) {return step;}vis.insert(tmp);que.push(tmp);}}}}}return -1;
}

給定一個由 0 和 1 組成的矩陣 mat ，請輸出一個大小相同的矩陣，其中每一個格子是 mat 中對應位置元素到最近的 0 的距離。

兩個相鄰元素間的距離為 1 。

示例 1：

輸入：mat = [[0,0,0],[0,1,0],[0,0,0]]
輸出：[[0,0,0],[0,1,0],[0,0,0]]

示例 2：

輸入：mat = [[0,0,0],[0,1,0],[1,1,1]]
輸出：[[0,0,0],[0,1,0],[1,2,1]]

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• mat[i][j] is either 0 or 1.
• mat 中至少有一個 0

const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {// 正難則反// 把0當作起點，1當作終點int m = mat.size(), n = mat[0].size();vector<vector<bool>> vis(m, vector<bool>(n, false));queue<pair<int, int>> que;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (mat[i][j] == 0) {que.emplace(i, j);vis[i][j] = true;}}}vector<vector<int>> ans(mat);int step = 0;while (!que.empty()) {step++;int cnt = que.size();while (cnt--) {auto [x, y] = que.front();que.pop();for (int k = 0; k < 4; ++k) {int nx = x + dx[k], ny = y + dy[k];if (nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny]) {vis[nx][ny] = true;ans[nx][ny] = step;que.emplace(nx, ny);}}}}return ans;
}

優化

const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {// 正難則反// 把0當作起點，1當作終點int m = mat.size(), n = mat[0].size();vector<vector<int>> dist(m, vector<int>(n, -1));queue<pair<int, int>> que;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (mat[i][j] == 0) {que.emplace(i, j);dist[i][j] = 0;}}}while (!que.empty()) {auto [x, y] = que.front();que.pop();for (int k = 0; k < 4; ++k) {int nx = x + dx[k], ny = y + dy[k];if (nx >= 0 && nx < m && ny >= 0 && ny < n && dist[nx][ny] == -1) {dist[nx][ny] = dist[x][y] + 1;que.emplace(nx, ny);}}}return dist;
}

你現在手里有一份大小為 n x n 的 網格 grid，上面的每個 單元格 都用 0 和 1 標記好了。其中 0 代表海洋，1 代表陸地。

請你找出一個海洋單元格，這個海洋單元格到離它最近的陸地單元格的距離是最大的，并返回該距離。如果網格上只有陸地或者海洋，請返回 -1。

我們這里說的距離是「曼哈頓距離」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 這兩個單元格之間的距離是 |x0 - x1| + |y0 - y1| 。

示例 1：

輸入：grid = [[1,0,1],[0,0,0],[1,0,1]]
輸出：2
解釋： 
海洋單元格 (1, 1) 和所有陸地單元格之間的距離都達到最大，最大距離為 2。

示例 2：

輸入：grid = [[1,0,0],[0,0,0],[0,0,0]]
輸出：4
解釋： 
海洋單元格 (2, 2) 和所有陸地單元格之間的距離都達到最大，最大距離為 4。

提示：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 100
• grid[i][j] 不是 0 就是 1

const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {1, -1, 0, 0};int maxDistance(vector<vector<int>>& grid) {queue<pair<int, int>> que;int m = grid.size(), n = grid[0].size();vector<vector<int>> dist(m, vector<int>(n, -1));for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == 1) {que.emplace(i, j);dist[i][j] = 0;}}}int ans = -1;while (!que.empty()) {auto [x, y] = que.front();que.pop();for (int k = 0; k < 4; ++k) {int nx = x + dx[k], ny = y + dy[k];if (nx >= 0 && nx < m && ny >= 0 && ny < n && dist[nx][ny] == -1) {dist[nx][ny] = dist[x][y] + 1;ans = max(ans, dist[nx][ny]);que.emplace(nx, ny);}}}return ans;
}

給你一個大小為 m x n 的整數矩陣 isWater ，它代表了一個由 陸地 和 水域 單元格組成的地圖。

• 如果 isWater[i][j] == 0 ，格子 (i, j) 是一個 陸地 格子。
• 如果 isWater[i][j] == 1 ，格子 (i, j) 是一個 水域 格子。

你需要按照如下規則給每個單元格安排高度：

• 每個格子的高度都必須是非負的。
• 如果一個格子是 水域 ，那么它的高度必須為 0 。
• 任意相鄰的格子高度差 至多 為 1 。當兩個格子在正東、南、西、北方向上相互緊挨著，就稱它們為相鄰的格子。（也就是說它們有一條公共邊）

找到一種安排高度的方案，使得矩陣中的最高高度值 最大 。

請你返回一個大小為 m x n 的整數矩陣 height ，其中 height[i][j] 是格子 (i, j) 的高度。如果有多種解法，請返回 任意一個 。

示例 1：

輸入：isWater = [[0,1],[0,0]]
輸出：[[1,0],[2,1]]
解釋：上圖展示了給各個格子安排的高度。
藍色格子是水域格，綠色格子是陸地格。

示例 2：

輸入：isWater = [[0,0,1],[1,0,0],[0,0,0]]
輸出：[[1,1,0],[0,1,1],[1,2,2]]
解釋：所有安排方案中，最高可行高度為 2 。
任意安排方案中，只要最高高度為 2 且符合上述規則的，都為可行方案。

提示：

• m == isWater.length
• n == isWater[i].length
• 1 <= m, n <= 1000
• isWater[i][j] 要么是 0 ，要么是 1 。
• 至少有 1 個水域格子。

**注意：**本題與 542 題相同。

const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {queue<pair<int, int>> que;int m = isWater.size(), n = isWater[0].size();vector<vector<int>> ans(m, vector<int>(n, -1));for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (isWater[i][j] == 1) {que.emplace(i, j);ans[i][j] = 0;}}}while (!que.empty()) {auto [x, y] = que.front();que.pop();for (int k = 0; k < 4; ++k) {int nx = x + dx[k], ny = y + dy[k];if (nx >= 0 && nx < m && ny >= 0 && ny < n && ans[nx][ny] == -1) {ans[nx][ny] = ans[x][y] + 1;que.emplace(nx, ny);}}}return ans;
}

給你一個 m x n 的迷宮矩陣 maze （下標從 0 開始），矩陣中有空格子（用 '.' 表示）和墻（用 '+' 表示）。同時給你迷宮的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一開始所在格子的行和列。

每一步操作，你可以往 上，下，左 或者 右 移動一個格子。你不能進入墻所在的格子，你也不能離開迷宮。你的目標是找到離 entrance 最近 的出口。出口 的含義是 maze 邊界 上的 空格子。entrance 格子 不算 出口。

請你返回從 entrance 到最近出口的最短路徑的 步數 ，如果不存在這樣的路徑，請你返回 -1 。

示例 1：

輸入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
輸出：1
解釋：總共有 3 個出口，分別位于 (1,0)，(0,2) 和 (2,3) 。
一開始，你在入口格子 (1,2) 處。
- 你可以往左移動 2 步到達 (1,0) 。
- 你可以往上移動 1 步到達 (0,2) 。
從入口處沒法到達 (2,3) 。
所以，最近的出口是 (0,2) ，距離為 1 步。

示例 2：

輸入：maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
輸出：2
解釋：迷宮中只有 1 個出口，在 (1,2) 處。
(1,0) 不算出口，因為它是入口格子。
初始時，你在入口與格子 (1,0) 處。
- 你可以往右移動 2 步到達 (1,2) 處。
所以，最近的出口為 (1,2) ，距離為 2 步。

示例 3：

輸入：maze = [[".","+"]], entrance = [0,0]
輸出：-1
解釋：這個迷宮中沒有出口。

提示：

• maze.length == m
• maze[i].length == n
• 1 <= m, n <= 100
• maze[i][j] 要么是 '.' ，要么是 '+' 。
• entrance.length == 2
• 0 <= entrancerow < m
• 0 <= entrancecol < n
• entrance 一定是空格子。

BFS層序遍歷，每次step++，第一次到達邊界時就是最短路徑，vis數組判斷是否訪問過該節點。

const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {int m = maze.size(), n = maze[0].size();vector<vector<bool>> vis(m, vector<bool>(n, false));queue<pair<int, int>> que;que.emplace(entrance[0], entrance[1]);vis[entrance[0]][entrance[1]] = true;int step = 0;while (!que.empty()) {step++;int cnt = que.size();while (cnt--) {auto [x, y] = que.front();que.pop();for (int k = 0; k < 4; ++k) {int nx = x + dx[k], ny = y + dy[k];if (nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny]) {vis[nx][ny] = true;if (maze[nx][ny] == '.') {if (nx == 0 || nx == m - 1 || ny == 0 || ny == n - 1) {return step;}que.emplace(nx, ny);}}}}}return -1;
}

字典 wordList 中從單詞 beginWord 到 endWord 的 轉換序列 是一個按下述規格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

• 每一對相鄰的單詞只差一個字母。
• 對于 1 <= i <= k 時，每個 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
• sk == endWord

給你兩個單詞 beginWord 和 endWord 和一個字典 wordList ，返回 從 beginWord 到 endWord 的 最短轉換序列 中的 單詞數目 。如果不存在這樣的轉換序列，返回 0 。

示例 1：

輸入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
輸出：5
解釋：一個最短轉換序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的長度 5。

示例 2：

輸入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
輸出：0
解釋：endWord "cog" 不在字典中，所以無法進行轉換。

提示：

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord、endWord 和 wordList[i] 由小寫英文字母組成
• beginWord != endWord
• wordList 中的所有字符串 互不相同

和這題類似433. 最小基因變化

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {if (beginWord == endWord) {return 0;}unordered_set<string> vis;unordered_set<string> hash(wordList.begin(), wordList.end());if (!hash.count(endWord)) {return 0;}int step = 1;int n = beginWord.size();queue<string> que;que.push(beginWord);vis.insert(beginWord);while (!que.empty()) {step++;int cnt = que.size();while (cnt--) {string str = que.front();que.pop();for (int i = 0; i < n; ++i) {string tmp = str;for (char ch = 'a'; ch <= 'z'; ++ch) {tmp[i] = ch;if  (hash.count(tmp) && !vis.count(tmp)) {if (tmp == endWord) {return step;}vis.insert(tmp);que.push(tmp);}}}}}return 0;
}

你被請來給一個要舉辦高爾夫比賽的樹林砍樹。樹林由一個 m x n 的矩陣表示， 在這個矩陣中：

• 0 表示障礙，無法觸碰
• 1 表示地面，可以行走
• 比 1 大的數 表示有樹的單元格，可以行走，數值表示樹的高度

每一步，你都可以向上、下、左、右四個方向之一移動一個單位，如果你站的地方有一棵樹，那么你可以決定是否要砍倒它。

你需要按照樹的高度從低向高砍掉所有的樹，每砍過一顆樹，該單元格的值變為 1（即變為地面）。

你將從 (0, 0) 點開始工作，返回你砍完所有樹需要走的最小步數。 如果你無法砍完所有的樹，返回 -1 。

可以保證的是，沒有兩棵樹的高度是相同的，并且你至少需要砍倒一棵樹。

示例 1：

輸入：forest = [[1,2,3],[0,0,4],[7,6,5]]
輸出：6
解釋：沿著上面的路徑，你可以用 6 步，按從最矮到最高的順序砍掉這些樹。

示例 2：

輸入：forest = [[1,2,3],[0,0,0],[7,6,5]]
輸出：-1
解釋：由于中間一行被障礙阻塞，無法訪問最下面一行中的樹。

示例 3：

輸入：forest = [[2,3,4],[0,0,5],[8,7,6]]
輸出：6
解釋：可以按與示例 1 相同的路徑來砍掉所有的樹。
(0,0) 位置的樹，可以直接砍去，不用算步數。

提示：

• m == forest.length
• n == forest[i].length
• 1 <= m, n <= 50
• 0 <= forest[i][j] <= 109

每次要砍一棵樹都是一次BFS求最短路。

const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};int cutOffTree(vector<vector<int>>& forest) {vector<pair<int, int>> trees;int m = forest.size(), n = forest[0].size();for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (forest[i][j] > 1) {trees.emplace_back(i, j);}}}auto cmp = [&](const pair<int, int>& a, const pair<int, int>& b) {return forest[a.first][a.second] < forest[b.first][b.second];};sort(trees.begin(), trees.end(), cmp);int ans = 0;int bx = 0, by = 0;for (auto [ex, ey] : trees) {int step = bfs(forest, bx, by, ex, ey);if (step == -1) {return -1;}ans += step;bx = ex, by = ey;}return ans;
}bool vis[55][55];
int bfs(vector<vector<int>>& forest, int bx, int by, int ex, int ey) { if (bx == ex && by == ey) {return 0;}int m = forest.size(), n = forest[0].size();memset(vis, 0, sizeof(vis));queue<pair<int, int>> que;que.emplace(bx, by);int step = 0;while (!que.empty()) {step++;int cnt = que.size();while (cnt--) {auto [x, y] = que.front();que.pop();for (int k = 0; k < 4; ++k) {int nx = x + dx[k], ny = y + dy[k];if (nx >= 0 && nx < m && ny >= 0 && ny < n && forest[nx][ny] != 0 && vis[nx][ny] == false) {if (nx == ex && ny == ey) {return step;}vis[nx][ny] = true;que.emplace(nx, ny);}}}}return -1;
}