Skip to content

Instantly share code, notes, and snippets.

@alldroll
Created July 4, 2020 22:01
Show Gist options
  • Save alldroll/73b0b4ab8367f5072a05ddaf0af0adcb to your computer and use it in GitHub Desktop.
Save alldroll/73b0b4ab8367f5072a05ddaf0af0adcb to your computer and use it in GitHub Desktop.
const (
water = 0
land = 1
visited = 2
)
var directions = [][2]int{
{0, 1},
{1, 0},
{0, -1},
{-1, 0},
}
// 0,0,0,0,1,1,1
// 1,1,1,1,1,1,1
// 0,0,0,0,0,0,0
// 0,0,0,0,1,1,1
// 1,1,1,1,1,1,0
// 0,0,0,1,0,0,0
func numDistinctIslands(grid [][]int) int {
set := make(map[string]bool)
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[0]); j++ {
if grid[i][j] == land {
hash := markAsVisited(grid, i, j)
if _, ok := set[hash]; !ok {
set[hash] = true
}
}
}
}
return len(set)
}
// **
// **
// **
// **
// **
// **
func markAsVisited(grid [][]int, i, j int) string {
hash := ""
n, m := len(grid), len(grid[0])
grid[i][j] = visited
queue := [][2]int{{i, j}}
for len(queue) > 0 {
item := queue[0]
hash += fmt.Sprintf("%d", (item[0] - i) * 2 * len(grid) + (item[1] - j))
queue = queue[1:]
for _, d := range directions {
x, y := item[0] + d[0], item[1] + d[1]
if x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == land {
grid[x][y] = visited
queue = append(queue, [2]int{x, y})
}
}
}
return hash
}
func equals(grid [][]int, i, j, m, n int) bool {
return false
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment