463. Периметр острова
Эта статья переведена автоматически с английский на русский. Оригинал доступен на английский.
Решение задачи 463 “Island Perimeter” (Периметр острова) с LeetCode.
Задача
Дана сетка размером row x col, представляющая карту, где grid[i][j] = 1 представляет землю, а grid[i][j] = 0 представляет воду.
Ячейки сетки соединены горизонтально/вертикально (не по диагонали). Сетка полностью окружена водой, и существует ровно один остров (то есть одна или более связанных ячеек с землей).
На острове нет “озер”, то есть вода внутри не связана с водой вокруг острова. Одна ячейка - это квадрат со стороной длиной 1. Сетка прямоугольная, ширина и высота не превышают 100. Определите периметр острова.
Пример 1:
Вход: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Выход: 16
Объяснение: Периметр - это 16 желтых полос на изображении выше.
Пример 2:
Вход: grid = [[1]]
Выход: 4
Пример 3:
Вход: grid = [[1,0]]
Выход: 4
Ограничения:
row == grid.length
col == grid[i].length
1 <= row, col <= 100
grid[i][j] равно 0 или 1.
В сетке ровно один остров.
Решение
Поиск в ширину (Breadth First Search)
func islandPerimeter(grid [][]int) int {
q := [][]Pos{}
vis := map[Pos]bool{}
per := 0
found := false
for idx:=0;idx<len(grid)&&!found;idx++ {
for jdx:=0;jdx<len(grid[idx])&&!found;jdx++ {
p:= Pos{X:idx, Y:jdx}
if grid[idx][jdx] == 1 {
vis[p] = true
found = true
q = append(q, []Pos{p})
}
}
}
dir := [][]int{
{-1, 0},
{1, 0},
{0, -1},
{0, 1},
}
for idx:=0;idx<len(q);idx++ {
d := []Pos{}
qi := q[idx]
for jdx := range qi {
el := qi[jdx]
for dix :=range dir{
dx:=dir[dix][0]
dy:=dir[dix][1]
pp := Pos{X:el.X+dx,Y: el.Y+dy}
if _, ok := vis[pp];!ok {
if check(grid, pp) {
vis[pp] = true
d = append(d, pp)
}else{
per++
}
}
}
}
if len(d)>0{
q = append(q, d)
}
}
return per
}
func check(grid [][]int, p Pos) bool {
if p.X>=0 && p.X<len(grid) && p.Y>=0 && p.Y<len(grid[0]){
return grid[p.X][p.Y]==1
}
return false
}
type Pos struct {
X int
Y int
}