package top100liked

import (
	"fmt"
	"testing"
)

// https://leetcode.cn/problems/number-of-islands/?envType=study-plan-v2&envId=top-100-liked

func numIslands(grid [][]byte) int {
	m := len(grid)
	n := len(grid[0])
	visited := make([][]bool, m)
	for i := range m {
		visited[i] = make([]bool, n)
	}
	res := 0
	type point struct {
		Row    int
		Column int
	}
	queue := []point{}
	for i := range m {
		for j := range n {
			if !visited[i][j] && grid[i][j] == '1' {
				queue = append(queue, point{i, j})
				visited[i][j] = true
				res++
			}
			for len(queue) > 0 {
				cur := queue[0]
				queue = queue[1:]
				// 左侧
				if cur.Column > 0 && !visited[cur.Row][cur.Column-1] && grid[cur.Row][cur.Column-1] == '1' {
					queue = append(queue, point{cur.Row, cur.Column - 1})
					visited[cur.Row][cur.Column-1] = true
				}
				// 右侧
				if cur.Column+1 < n && !visited[cur.Row][cur.Column+1] && grid[cur.Row][cur.Column+1] == '1' {
					queue = append(queue, point{cur.Row, cur.Column + 1})
					visited[cur.Row][cur.Column+1] = true
				}
				// 上侧
				if cur.Row > 0 && !visited[cur.Row-1][cur.Column] && grid[cur.Row-1][cur.Column] == '1' {
					queue = append(queue, point{cur.Row - 1, cur.Column})
					visited[cur.Row-1][cur.Column] = true
				}
				// 下侧
				if cur.Row+1 < m && !visited[cur.Row+1][cur.Column] && grid[cur.Row+1][cur.Column] == '1' {
					queue = append(queue, point{cur.Row + 1, cur.Column})
					visited[cur.Row+1][cur.Column] = true
				}
			}
		}
	}
	return res
}

func Test(t *testing.T) {
	input := [][]byte{{'1', '1', '1'}, {'0', '1', '0'}, {'1', '1', '1'}}
	fmt.Println(numIslands(input))
}