Memory Usage: 26.4 MB, less than14.29%ofC++online submissions forIsland Perimeter.
LeetCode #463
Q.
You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water.
Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).
The island doesn't have "lakes" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.
2차원 정수 그리드로 된 지도를 받는데, 육지는 1, 물은 0 으로 표기되어 있다. 그리드 칸들은 가로세로 (대각선제외)로 연결되어 있다. 그리드는 전부 물로 둘러싸여있고, 최소 한개의 육지가 있다.
육지는 강이 없다 (육지로 둘러쌓인 물 부분이 없다). 하나의 셀은 한변당 거리가 1이다. 그리드는 사각형이고, 가로세로 길이는 100을 넘지 않는다. 섬의 둘레를 구하여라.
Explanation: The perimeter is the 16 yellow stripes in the image below:
Process
// Process //1. Input 2d grid //2. Make extentedGrid //3. Iterate extendedGrid (i) // 3.1. Iterate center of extendedGrid[i] (j) // 3.1.1. Check if it's 0 // 3.1.1.1. If so -> count number surrounded 1 // 3.1.2. Add to resultCount //4. Return resultCount
// 처리과정
//1. 2차원 배열 입력받는다.
//2. 확장시킨 배열을 만들어둔다.
//3. 확장배열 중심부를 반복한다 (i)
// 3.1. 확장배열 중심부를 반복한다 (j)
// 3.1.1. 0 인지 확인해서
// 3.1.1.1. 0이면 -> 1로 둘러쌓인 개수를 센다.
// 3.1.2. 결과갯수에 개수를 더한다.
//4. 결과갯수 반환한다.
Code.. lemme see example code!!!
코드.. 예제코드를 보자!!!
class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
int resultCount = 0;
// 2.
vector<int> tempVec;
for (int i = 0; i < grid[0].size(); ++i) {
tempVec.push_back(0);
}
grid.insert(grid.begin(), tempVec);
grid.insert(grid.begin(), tempVec);
grid.insert(grid.end(), tempVec);
grid.insert(grid.end(), tempVec);
for (int i = 0; i < grid.size(); ++i) {
grid[i].insert(grid[i].begin(), 0);
grid[i].insert(grid[i].begin(), 0);
grid[i].insert(grid[i].end(), 0);
grid[i].insert(grid[i].end(), 0);
}
// 2.
//vector<vector<int>> extendedGrid;
//for (int i = 0; i < grid.size() + 4; ++i) {
// vector<int> tempVector;
// extendedGrid.push_back(tempVector);
// for (int j = 0; j < grid[0].size() + 4; ++j) {
// extendedGrid[i].push_back(0);
// }
//}
//for (int i = 2; i < grid.size() + 2; ++i) {
// for (int j = 2; j < grid[0].size() + 2; ++j) {
// extendedGrid[i][j] = grid[i - 2][j - 2];
// }
//}
// 3.
for (int i = 1; i < grid.size() - 1; ++i) {
int count = 0;
for (int j = 1; j < grid[i].size() - 1; ++j) {
if (grid[i][j] == 0) {
if (grid[i - 1][j] == 1)
++count;
if (grid[i + 1][j] == 1)
++count;
if (grid[i][j - 1] == 1)
++count;
if (grid[i][j + 1] == 1)
++count;
}
}
resultCount += count;
}
// 4.
return resultCount;
}
};
