## Sunday, November 20, 2016

### LeetCode 463 - Island Perimeter

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.
Example:

```[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]

Explanation: The perimeter is the 16 yellow stripes in the image below:

```
http://blog.csdn.net/mebiuw/article/details/53265123
public int islandPerimeter(int[][] grid) { int permeter = 0; int n = grid.length; int m = grid[0].length; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(grid[i][j] == 1){ if(i==0 || grid[i-1][j] == 0) permeter++; if(i==n-1 || grid[i+1][j] == 0) permeter++; if(j==0 || grid[i][j-1] == 0) permeter++; if(j==m-1 || grid[i][j+1] == 0) permeter++; } } } return permeter; }
http://blog.csdn.net/jmspan/article/details/53254264

1.     public int islandPerimeter(int[][] grid) {
2.         int p = 0;
3.         for(int i = 0; i < grid.length; i++) {
4.             for(int j = 0; j < grid[i].length; j++) {
5.                 if (grid[i][j] == 0continue;
6.                 if (i == 0 || grid[i - 1][j] == 0) p++;
7.                 if (i == grid.length - 1 || grid[i + 1][j] == 0) p++;
8.                 if (j == 0 || grid[i][j - 1] == 0) p++;
9.                 if (j == grid[i].length - 1 || grid[i][j + 1] == 0) p++;
10.             }
11.         }
12.         return p;
13.     }

``````public static int islandPerimeter(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
int result = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
result += 4;
if (i > 0 && grid[i-1][j] == 1) result -= 2;
if (j > 0 && grid[i][j-1] == 1) result -= 2;
}
}
}
return result;
}``````

X.
https://discuss.leetcode.com/topic/68786/clear-and-easy-java-solution
1. loop over the matrix and count the number of islands;
2. if the current dot is an island, count if it has any right neighbour or down neighbour;
3. the result is islands * 4 - neighbours * 2
``````    public int islandPerimeter(int[][] grid) {
int islands = 0, neighbours = 0;

for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == 1) {
islands++; // count islands
if (i < grid.length - 1 && grid[i + 1][j] == 1) neighbours++; // count down neighbours
if (j < grid[i].length - 1 && grid[i][j + 1] == 1) neighbours++; // count right neighbours
}
}
}

return islands * 4 - neighbours * 2;
}``````
X. DFS
https://discuss.leetcode.com/topic/68751/easy-dfs-solution-explaination-without-visited-array
he idea here is that each land cell contributes as many lines in perimeter as it's surrounded by water / boundary.
``````void dfs(vector<vector<int>>& b, int *ans, int i, int j) {
if (i < 0 || i >= b.size() || j < 0 || j >= b[0].size() || b[i][j] != 1)
return;
b[i][j] = -1; // mark it as visited
*ans += (j + 1 >= b[0].size() || b[i][j+1] == 0) /* right */ +
(i - 1 < 0            || b[i-1][j] == 0) /* top */ +
(j - 1 < 0            || b[i][j-1] == 0) /* left */ +
(i + 1 >= b.size()    || b[i+1][j] == 0) /* bottom */;
dfs(b, ans, i, j + 1);
dfs(b, ans, i - 1, j);
dfs(b, ans, i, j - 1);
dfs(b, ans, i + 1, j);
return;
}
int islandPerimeter(vector<vector<int>>& grid) {
int ans = 0, i, j;
for (i = 0; i < grid.size(); i++) {
for (j = 0; j < grid[0].size(); j++) {
if (grid[i][j]) {
dfs(grid, &ans, i, j);
return ans;
}
}
}
return 0;
}``````

```public int islandPerimeter(int[][] grid) {
boolean[][] mark = new boolean[grid.length][grid[0].length];
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
mark[i][j] = true;
count++;
} else {
mark[i][j] = false;
}
}
}
int perimeter = count * 4;
System.out.println("perimeter:" + perimeter);
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (mark[i][j]) {
perimeter -= neigbors(i, j, mark); //减去相邻的点
}
}
}
return perimeter;
}

private int neigbors(int i, int j, boolean[][] mark) {
int count = 0;
for (int x = -1; x <= 1; x += 2) {
int tempx = x + i;
int tempy = j;
if (isSafe(tempx, tempy, mark.length, mark[0].length) && mark[tempx][tempy]) {
count++;
}
}
for (int y = -1; y <= 1; y += 2) {
int tempx = i;
int tempy = y + j;
if (isSafe(tempx, tempy, mark.length, mark[0].length) && mark[tempx][tempy]) {
count++;
}
}
System.out.printf("i:%d,j:%d\n", i, j);
System.out.println("count:" + count);
return count;
}

private boolean isSafe(int x, int y, int xlength, int ylength) {
if (x < 0 || x >= xlength || y < 0 || y >= ylength) {
return false;
} else {
return true;
}
}```
http://www.geeksforgeeks.org/find-perimeter-shapes-formed-1s-binary-matrix/
The idea is to traverse the matrix, find all ones and find their contribution in perimeter. The maximum contribution of a 1 is four if it is surrounded by all 0s. The contribution reduces by one with 1 around it.
Algorithm for solving this problem:
1. Traverse the whole matrix and find the cell having value equal to 1.
2. Calculate the number of closed side for that cell and add, 4 – number of closed side to the total perimeter.
`int` `numofneighbour(``int` `mat[][C], ``int` `i, ``int` `j)`
`{`
`    ``int` `count = 0;`
`    ``// UP`
`    ``if` `(i > 0 && mat[i - 1][j])`
`        ``count++;`
`    ``// LEFT`
`    ``if` `(j > 0 && mat[i][j - 1])`
`        ``count++;`
`    ``// DOWN`
`    ``if` `(i < R-1 && mat[i + 1][j])`
`        ``count++;`
`    ``// RIGHT`
`    ``if` `(j < C-1 && mat[i][j + 1])`
`        ``count++;`
`    ``return` `count;`
`}`
`// Returns sum of perimeter of shapes formed with 1s`
`int` `findperimeter(``int` `mat[R][C])`
`{`
`    ``int` `perimeter = 0;`
`    ``// Traversing the matrix and finding ones to`
`    ``// calculate their contribution.`
`    ``for` `(``int` `i = 0; i < R; i++)`
`        ``for` `(``int` `j = 0; j < C; j++)`
`            ``if` `(mat[i][j])`
`                ``perimeter += (4 - numofneighbour(mat, i ,j));`
`    ``return` `perimeter;`
`}`