Tác giả: Lê Trung Kiên lớp java 08
Email: lekien.2803.cg@gmail.com
SĐT: 0942096947
Link bài toán: https://leetcode.com/problems/island-perimeter/
1. Mở đầu
Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.
2. Đề bài
Cho một ma trận grid với kích thước row x col biểu thị cho một bản đồ, trong đó grid[i][j] = 1 thì tượng trưng cho đất liền, grid[i][j] = 0 tượng trưng cho nước biển.
Các ô trong bản đồ grid được kết nối với nhau theo chiều ngang/chiều dọc (không kết nối theo đường chéo). grid được bao quanh hoàn toàn bởi nước, tuy nhiên chắc chắn có một hòn đảo ở trong đó(nghĩa là một hoặc nhiều ô đất được kết nối với nhau).
Hòn đảo trong grid sẽ không có “hồ”, nghĩa là nước bên trong không được kết nối với nước xung quanh đảo. Một ô là một hình vuông có cạnh dài bằng 1. Xác định chu vi của hòn đảo.
Điều kiện:
row == grid.length.col == grid[i].length.1 <= row, col <= 100.grid[i][j]có giá trị là0hoặc1.- Luôn có một hòn đảo ở trong
grid.
Bài toán minh họa 1:
Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.
Bài toán minh họa 2:
Input: grid = [[1]]
Output: 4
bài toán minh họa 3:
Input: grid = [[1,0]]
Output: 4
3. Phân tích
Ố kề! Bài này đọc qua thì thấy có vẻ phức tạp, nhưng chúng ta hãy cùng phân tích, bóc tách đề bài nhé!
Đầu tiên khi nhìn vào đề bài, chúng ta biết được rằng grid chính là mảng hai chiều, vậy thì chúng ta sẽ cần có hai vòng lặp lồng nhau, một cái chạy hết các hàng, một cái chạy hết các cột trong mảng hai chiều này.
Người ta yêu cầu chúng ta tính được chu vi của hòn đảo, mỗi ô đất thì có cạnh bằng 1, vậy thì ô đất có chu vi bằng 4. Vậy là cứ khi nào chúng ta gặp đất liền, chu vi sẽ được cộng thêm 4.
Tuy nhiên, khi các ô đất nối với nhau, phần bên trong sẽ không được tính, bởi vì chu vi là chúng ta chỉ được tính viền ngoài, tức là toàn bộ đoạn kẻ màu vàng ở đây:
Vì các ô được kết nối nhau qua chiều ngang và chiều dọc (không kết nối theo đường chéo) như đề bài, như vậy nghĩa là chúng ta phải làm thêm một bước kiểm tra nữa, ấy là kiểm tra xem ô liền kề phía bên trái, phía bên phải, phía dưới và phía trên của ô đất chúng ta đang xét có phải là đất hay không? Cứ ô liền kề nằm ở hướng nào là đất thì ta trừ chu vi đi 1, tại vì nó trùng nhau mà, ví dụ như ở đây grid[1][1] có cả bốn hướng đều là đất, nên chu vi sẽ bị trừ đi 4:
Sau khi xét hết các ô, ta sẽ có kết quả là chu vi của vùng đất đó.
4. Code chạy bằng cơm
Đầu tiên, ta sẽ xác định kích thước mỗi chiều của grid, hai kích thước này ta gọi là row và col tương ứng với số lượng hàng và cột của mảng hai chiều grid:
Bây giờ chúng ta dùng hai vòng lặp for để thực hiện việc kiểm tra từng ô một với hai con trỏ i và j:
Ô kê, giờ ta đặt điều kiện kiểm tra, nếu grid[i][j] == 1 tức là nếu ô chúng ta đang kiểm tra có giá trị là 1, nghĩa là ô đó là đất liền, chúng ta sẽ bắt đầu thực hiện việc kiểm tra để tính chu vi như đã nói ở trên:
Việc kiểm tra xem ô liền kề phía bên trái, bên phải, bên trên, bên dưới tôi sẽ tách ra thành một function riêng làm nhiệm vụ này. Mỗi khi gặp đất liền, chúng ta sẽ gọi function này để tính, sẽ có bốn trường hợp được xét tương ứng với bốn hướng của ô đó. Trước hết là phải kiểm tra ô đó vẫn nằm trong mảng hai chiều, đồng thời ô đó là đất liền, khi ấy chu vi sẽ bị trừ đi 1.
Lấy ví dụ tại vị trí grid[1][1]
Xét phía bên trái:
Xét phía bên trên:
Xét phía bên phải:
Xét phía bên dưới:
Cứ như thế đến hết mảng hai chiều, chúng ta sẽ có được giá trị cuối cùng chính là chu vi của vùng đất.
5. Code chạy bằng máy
Code của chúng ta sẽ có dạng như sau:
public static int islandPerimeter(int[][] grid) {
int totalP = 0;
int row = grid.length;
int col = grid[0].length;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == 1) {
totalP += getPerimeter(grid, i, j);
}
}
}
return totalP;
}
public static int getPerimeter(int[][] grid, int i, int j){
int perimeter = 4;
if (i - 1 >= 0 && grid[i-1][j] == 1) {
perimeter -= 1;
}
if (j - 1 >= 0 && grid[i][j-1] == 1) {
perimeter -= 1;
}
if (i + 1 < grid.length && grid[i+1][j] == 1) {
perimeter -= 1;
}
if (j + 1 < grid[0].length && grid[i][j + 1] == 1) {
perimeter -= 1;
}
return perimeter;
}
6. Kết thúc
Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!
Bình luận