算法分析课程博客分享 5
542. 01 矩阵(01 Matrix)
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1:
输入:
0 0 0
0 1 0
0 0 0
输出:
0 0 0
0 1 0
0 0 0
示例 2:
输入:
0 0 0
0 1 0
1 1 1
输出:
0 0 0
0 1 0
1 2 1
注意:
- 给定矩阵的元素个数不超过 10000。
- 给定矩阵中至少有一个元素是 0。
- 矩阵中的元素只在四个方向上相邻: 上、下、左、右。
解题思路:
刚开始的时候，我考虑过能否使用 O(V) 的复杂度来解决问题，但实际上，我们必须考虑所有的路径才可以得出结果。首先，我们对矩阵进行一次扫描，获得所有的 0 的位置，并将这些位置的距离值设为 0，其余位置的距离值设为 INT_MAX，然后从 0 开始进行广搜。对于一个 0 点，我们将其周围的四个点的距离值设为 1，然后将这四个点放入队列中；对于一个 1 点，若周围的一个点的距离值大于当前点距离值加一，我们就更新这个周围点的距离值，并将更新过的点放入队列中，否则不进行操作。具体代码如下:
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty())
return vector<vector<int>>();
vector<vector<int>> dis(matrix.size(), vector<int>(matrix[0].size(), INT_MAX));
queue<pair<int, int>> q;
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[i].size(); ++j) {
if (matrix[i][j] == 0) {
q.push(make_pair(i, j));
dis[i][j] = 0;
}
}
}
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
for (int i = 0; i < 4; ++i) {
int x = cur.first + dir[i][0], y = cur.second + dir[i][1];
if (x >= 0 && x < matrix.size() && y >= 0 && y < matrix[0].size()) {
if (dis[x][y] > dis[cur.first][cur.second] + 1) {
dis[x][y] = dis[cur.first][cur.second] + 1;
q.push(make_pair(x, y));
}
}
}
}
return dis;
}
private:
int dir[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
200. 岛屿的个数(Number of Islands)
给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
解题思路:
这道题和上一题的思路类似，但是，因为这道题与广搜的路径无关，所以我们可以使用 O(V) 复杂度解决这个问题。我们首先对矩阵进行扫描，当检测到值为 1 的点的时候，代表我们发现了一个岛，这时候我们要令 count 的值加一。然后，我们从当前检测到的点开始进行广搜，把与其属于同一个岛的点全部设为 0，以确保我们在扫描矩阵时不会扫描到属于同一个岛的多个值为 1 的点。最后，count 的值就是岛屿的个数，具体代码如下:
public:
int numIslands(vector<vector<char>>& grid) {
int count = 0;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == '1') {
++count;
bfs(grid, i, j);
}
}
}
return count;
}
private:
int dir[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
void bfs(vector<vector<char>>& grid, int x, int y) {
if (grid[x][y] == '0')
return;
grid[x][y] = '0';
for (int i = 0; i < 4; ++i) {
int nextX = x + dir[i][0], nextY = y + dir[i][1];
if (nextX >= 0 && nextX < grid.size() && nextY >= 0 && nextY < grid[0].size()) {
bfs(grid, nextX, nextY);
}
}
}
773. 滑动谜题(Sliding Puzzle)
在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1&126;5 来表示, 以及一块空缺用 0 来表示。
一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换。
最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
示例：
输入：board = [[1,2,3],[4,0,5]]
输出：1
解释：交换 0 和 5 ，1 步完成
输入：board = [[1,2,3],[5,4,0]]
输出：-1
解释：没有办法完成谜板
输入：board = [[4,1,2],[5,0,3]]
输出：5
解释：
最少完成谜板的最少移动次数是 5 ，
一种移动路径:
尚未移动: [[4,1,2],[5,0,3]]
移动 1 次: [[4,1,2],[0,5,3]]
移动 2 次: [[0,1,2],[4,5,3]]
移动 3 次: [[1,0,2],[4,5,3]]
移动 4 次: [[1,2,0],[4,5,3]]
移动 5 次: [[1,2,3],[4,5,0]]
输入：board = [[3,2,4],[1,5,0]]
输出：14
提示：
- board 是一个如上所述的 2 x 3 的数组.
- board&91;i&93;&91;j&93; 是一个 [0, 1, 2, 3, 4, 5] 的排列.
解题思路:
在参考了网上的解法后，我发现在这道题上可以应用很多巧妙的小技巧，所以觉得有必要在这里记录一下。
首先，我以前处理 bfs 的时候，基本上都是用一个矩阵来表示节点是否被访问过。但是，在这道题中，我们可能需要重复访问同一个节点，而且我们需要关注的是所有元素的位置是否被正确摆放。由于我们关注的不再是单独某一个点的值，我们需要将访问过的状态以哈希的方式储存起来，以通过 bfs 穷举所有的可能状态。根据题目的描述，我们可以保证输入矩阵的维度是 2 x 3，因此，实际上，我们可以用一个字符串来表示当前矩阵的状态。而当我们使用字符串表示时，我们就不能像平时一样来获得相邻的点的坐标。由于我们已经知道了矩阵的维度，对于一个点，其相邻的点的坐标其实可以提前计算出来。因此，我们使用一个 dir 数组作为边缘链表，以在 bfs 时获得相邻的点。具体代码如下：
public:
int slidingPuzzle(vector<vector<int>>& board) {
string dest = "123450";
string dept = "";
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 3; ++j) {
dept += char(board[i][j]+'0');
}
}
int step = 0;
unordered_set<string> visited{dept};
queue<string> q{ {dept} };
while (!q.empty()) {
for (int i = q.size(); i > 0; --i) {
string cur = q.front();
q.pop();
if (cur == dest)
return step;
int zero = cur.find('0');
for (int adj : dir[zero]) {
string next = cur;
swap(next[zero], next[adj]);
if (visited.find(next) == visited.end()) {
visited.insert(next);
q.push(next);
}
}
}
++step;
}
return -1;
}
private:
vector<vector<int>> dir{ {1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4} };
考虑到上述的方法只能应用在维数已确定的矩阵上，我们在这里提出一种泛用性更强的解法。
public:
int slidingPuzzle(vector<vector<int>>& board) {
int r = board.size(), c = board[0].size();
state dest(vector<vector<int>>{ {1, 2, 3}, {4, 5, 0} }, make_pair(r-1, c-1));
state dept;
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
if (board[i][j] == 0) {
dept = state(board, make_pair(i, j));
}
}
}
int step = 0;
unordered_set<state, myHash> visited{dept};
queue<state> q{ {dept} };
while (!q.empty()) {
for (int i = q.size(); i > 0; --i) {
state cur = q.front();
q.pop();
if (cur == dest)
return step;
for (int j = 0; j < 4; ++j) {
int x = cur.zero.first + dir[j][0], y = cur.zero.second + dir[j][1];
if (x >= 0 && x < r && y >= 0 && y < c) {
state next = state(cur.board, make_pair(x, y));
swap(next.board[cur.zero.first][cur.zero.second], next.board[x][y]);
if (visited.find(next) == visited.end()) {
visited.insert(next);
q.push(next);
}
}
}
}
++step;
}
return -1;
}
private:
struct state {
state() {}
state(vector<vector<int>> board, pair<int, int> zero) : board(board), zero(zero) {}
state& operator=(const state& other) {
this->board = other.board;
this->zero = other.zero;
return *this;
}
bool operator==(const state& other) const {
return this->board == other.board;
}
vector<vector<int>> board;
pair<int, int> zero;
};
struct myHash {
size_t operator()(const state& s) const {
return s.zero.first + s.zero.second;
}
};
int dir[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };