surrounded regions
idea:
start from the edgescode:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36vector<vector<char>> board = {{'x', 'x', 'x', 'x'}, {'x', 'o', 'o', 'x'}, {'o', 'x', 'x', 'x'}, {'x', 'o', 'o', 'x'}};
int row = board.size();
int col = board[0].size();
for (int r = 0; r < row; r++) {
bfs(board, r, 0);
bfs(board, r, col - 1);
}
for (int c = 0; c < col; c++) {
bfs(board, 0, c);
bfs(board, row - 1, c);
}
for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
if (board[r][c] == 'w') {
board[r][c] = 'o';
}
if (board[r][c] == 'o') {
board[r][c] = 'w';
}
}
}
void bfs(vector<vector<char>>& board, int start_r, int start_c) {
int row = board.size();
int col = board[0].size();
vector<pair<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
queue<pair<int>> que({start_r, start_c});
for (auto& dir : dirs) {
int new_r = dir.first + start_r;
int new_c = dir.second + start_c;
}
}
200 Number of Islands
Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3
idea
bfscode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if not grid or len(grid) == 0:
return 0
self.grid = grid
self.n, self.m = len(grid), len(grid[0])
self.visited = [[False] * self.m for _ in range(self.n)]
ans = 0
for i in range(self.n):
for j in range(self.m):
if grid[i][j] == '1' and not self.visited[i][j]:
ans += 1
self.visited[i][j] = True
self.bfs(i, j)
return ans
def bfs(self, x, y):
dzs = zip([1, 0, -1, 0], [0, 1, 0, -1])
que = [(x, y)]
while que:
h = que.pop(0)
for dz in dzs:
x_, y_ = h[0] + dz[0], h[1] + dz[1]
if self.isValid(x_, y_) and not self.visited[x_][y_]:
self.visited[x_][y_] = True
que.append((x_, y_))
def isValid(self, x, y):
if x >= 0 and x <= self.n - 1 and \
y >= 0 and y <= self.m - 1 and \
self.grid[x][y] == '1':
return True
return False
695. Max Area of Island
Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
Example 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:
[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.
idea
bfscode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
if (grid.empty()) {
return 0;
}
int row = grid.size(), col = grid[0].size(), ans = 0;
for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
if (grid[r][c] == 1) {
ans = max(ans, area(grid, r, c));
}
}
}
return ans;
}
private:
static int area(vector<vector<int>>& grid, int r, int c) {
int row = grid.size(), col = grid[0].size(), area = 1;
queue<pair<int, int>> myq;
vector<int> dirs({-1, 0, 1, 0, -1});
myq.push({r, c});
grid[r][c] = 2;
while (!myq.empty()) {
int y = myq.front().first, x = myq.front().second;
myq.pop();
for (int i = 0; i < 4; i++) {
int new_y = y + dirs[i], new_x = x + dirs[i + 1];
if (new_y >=0 && new_y < row && new_x >= 0 && new_x < col && grid[new_y][new_x] == 1) {
grid[new_y][new_x] = 2;
area++;
myq.push({new_y, new_x});
}
}
}
return area;
}
};
286. Walls and Gates
You are given a m x n 2D grid initialized with these three possible values.
-1 - A wall or an obstacle.
0 - A gate.
INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.
Example:
Given the 2D grid:1
2
3
4
5
6
7
8
9
10INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF
After running your function, the 2D grid should be:
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4
idea
bfscode:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29class Solution(object):
def wallsAndGates(self, rooms):
"""
:type rooms: List[List[int]]
:rtype: void Do not return anything, modify rooms in-place instead.
"""
self.inf = 2**31 - 1
if not rooms or len(rooms) == 0:
return None
que = []
visited = {}
for i in range(len(rooms)):
for j in range(len(rooms[0])):
if rooms[i][j] == 0:
que.append((i, j))
visited[(i, j)] = True
while que:
h = que.pop(0)
i, j = h[0], h[1]
c = rooms[i][j]
for dx, dy in zip([0, 1, 0, -1], [1, 0, -1, 0]):
ii, jj = i + dx, j + dy
if ii < 0 or ii >= len(rooms) or jj < 0 or jj >= len(rooms[0]) or visited.get((ii, jj)) or rooms[ii][jj] == -1:
continue
que.append((ii, jj))
rooms[ii][jj] = c + 1
visited[(i, j)] = True