Aristides
Senior Member
Độ khó: medium
Đề bài: cho một ma trận m * n chỉ mang các giá trị 0 và 1. Hãy trả về một ma trận chứa các giá trị là khoảng cách gần nhất từ các phần tử mang giá trị 1 đến một phần tử gần nhất mang giá trị 0. Quy ước khoảng cách giữa 2 phần tử liền kề nhau là 1
Ví dụ:
Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]
giải thích: khoảng cách các phần tử mang giá trị 0 đến giá trị 0 gần nhất là 0
Khoảng cách từ phần tử 1 ở mat[2][2] cho đến phần tử 0 gần nhất là 1
Giới hạn:
m = mat.size()
n = mat[0].size()
1 <= m, n <= 10^4
1 <= m * n <= 10^4
Có ít nhất 1 phần tử mang giá trị 0
https://leetcode.com/problems/01-matrix/
Đề bài: cho một ma trận m * n chỉ mang các giá trị 0 và 1. Hãy trả về một ma trận chứa các giá trị là khoảng cách gần nhất từ các phần tử mang giá trị 1 đến một phần tử gần nhất mang giá trị 0. Quy ước khoảng cách giữa 2 phần tử liền kề nhau là 1
Ví dụ:
Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]
giải thích: khoảng cách các phần tử mang giá trị 0 đến giá trị 0 gần nhất là 0
Khoảng cách từ phần tử 1 ở mat[2][2] cho đến phần tử 0 gần nhất là 1
Giới hạn:
m = mat.size()
n = mat[0].size()
1 <= m, n <= 10^4
1 <= m * n <= 10^4
Có ít nhất 1 phần tử mang giá trị 0
https://leetcode.com/problems/01-matrix/
C++:
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
// Giải bằng quy hoạch động
if(mat.size() == 0) return mat; // Nếu mat rỗng, trả về mat
// Khởi tạo ma trận chứa kết quả, khoảng cách ban đầu = không xác định (INT_MAX - 1)
vector<vector<int>> result(mat.size(), vector<int>(mat[0].size(), INT_MAX - 1));
for(int i = 0; i < mat.size(); i++){
for(int j = 0; j < mat[0].size(); j++)
{
if(mat[i][j] == 0)
{
result[i][j] = 0; //Khoảng cách từ phần tử 0 đến phần tử 0 gần nhất = 0
}
if(i > 0) // Kiểm tra coi có tồn tại phần tử kề trên đầu không
{
// So sánh khoảng cách đang chứa với khoảng cách đến phần tử trên đầu
int nearest = std::min(result[i][j], result[i - 1][j] + 1);
result[i][j] = nearest;
}
if(j > 0) //Kiểm tra coi có phần tử kề bên trái không
{
// So sánh khoảng cách đến phần tử kề bên trái với khoảng cách đang chứa
int nearest = std::min(result[i][j], result[i][j - 1] + 1);
result[i][j] = nearest;
}
}
}
for(int i = mat.size() - 1; i >= 0 ; i--) // Loop thêm 1 vòng nữa. Nhưng lần này là loop ngược lại
{
for(int j = mat[0].size() - 1; j >= 0; j--)
{
if(i < mat.size() - 1) // So sánh phần tử kề ở dưới
{
int nearest = min(result[i + 1][j] + 1, result[i][j]);
result[i][j] = nearest;
}
if(j < mat[0].size() - 1) // So sánh phần tử kề bên phải
{
int nearest = min(result[i][j], result[i][j + 1] + 1);
result[i][j] = nearest;
}
}
}
return result;
}
};
Không hiểu ý bác lắm. Chính vì có tối đa 4 con đường khác nhau nên phải xét cả đường ở trên, đường ở dưới, đường bên trái và đường bên phải
. Nhưng việc thấy code lúc trước của mình cùi bắp cũng là một dấu hiệu tốt, chứng tỏ mình đã tiến bộ. 
