資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學01 矩陣在 C++ 中
假設我們有一個由 0 和 1 組成的矩陣，我們需要找到每個單元格到最近的 0 的距離。這裡相鄰單元格之間的距離為 1。
所以，如果輸入如下：
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
那麼輸出將是
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 2 | 1 |
為了解決這個問題，我們將遵循以下步驟：
定義一個大小為 4 x 2 的陣列 dir := {{1, 0}, {-1, 0}, {0, -1}, {0, 1}}
n := 行數，m := 列數
定義一個 (n x m) 階矩陣 ret 並將其填充為無窮大 (inf)
定義一個佇列 q
初始化 i := 0，當 i < n 時，更新 (i 加 1)，執行：
初始化 j := 0，當 j < m 時，更新 (j 加 1)，執行：
如果 matrix[i, j] 不為零，則：
ret[i, j] := 0
將 {i, j} 插入 q
初始化 lvl := 1，當 q 不為空時，更新 (lvl 加 1)，執行：
sz := q 的大小
當 sz 不為零時，每次迭代 sz 減 1，執行：
定義一個名為 curr 的對，它是 q 的首元素
從 q 中刪除元素
初始化 k := 0，當 k < 4 時，更新 (k 加 1)，執行：
nx := curr.first + dir[k, 0]
ny := curr.second + dir[k, 1]
如果 nx < 0 或 nx >= n 或 ny < 0 或 ny >= m 或 ret[nx, ny] < lvl，則：
ret[nx, ny] := lvl
將 {nx, ny} 插入 q
返回 ret
示例
讓我們看看下面的實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
vector < vector <int> > ret(n, vector <int>(m, INT_MAX));
queue < pair <int, int> > q;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(!matrix[i][j]){
ret[i][j] = 0;
q.push({i, j});
}
}
}
for(int lvl = 1; !q.empty(); lvl++){
int sz = q.size();
while(sz--){
pair <int, int> curr = q.front();
q.pop();
for(int k = 0; k < 4; k++){
int nx = curr.first + dir[k][0];
int ny = curr.second + dir[k][1];
if(nx < 0 || nx >= n || ny < 0 || ny >= m || ret[nx][ny] < lvl) continue;
ret[nx][ny] = lvl;
q.push({nx, ny});
}
}
}
return ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,0,0},{0,1,0},{1,1,1}};
print_vector(ob.updateMatrix(v));
}輸入
{{0,0,0},{0,1,0},{1,1,1}}輸出
[[0, 0, 0, ],[0, 1, 0, ],[1, 2, 1, ],]
更新於：2020年11月17日
179 次瀏覽
廣告