Find max number of connected colors in grid

Find_max_number_of_connected_colors_in_grid.go

package Google

import "testing"

// Find max number of connected colors in grid
// https://proglib.io/p/google-interview-task/?fbclid=IwAR2PXn_XqXQx97U3FLSFssVfDa1-m2P-T3yAJELEJoOWpNfcQjfyesOegpY

type si struct {
	r int
	c int
	next *si
}

type Stack struct {
	Size int32
	head *si
}

func (stack *Stack) Push(r, c int) {
	element := new(si)
	element.r = r
	element.c = c
	element.next = stack.head
	stack.head = element
	stack.Size++
}

func (stack *Stack) Pop() (r, c int) {
	if stack.head == nil {
		return -1, -1
	}

	e := stack.head

	stack.head  = stack.head.next
	stack.Size--

	return e.r, e.c
}

func (stack *Stack) IsEmpty() bool {
	return stack.head == nil
}

func Find_max_number_of_connected_colors_in_grid(grid [][]int) int {

	var result int

	rl := len(grid)
	if rl == 0 { return 0 }
	cl := len(grid[0])
	if cl == 0 { return 0 }

	s := Stack{}
	visited := make(map[[2]int] bool)

	dr := []int {-1, 1, 0, 0,}
	dc := []int { 0, 0, 1,-1,}

	for r:=0; r < rl; r++ {
		for c := 0; c < cl; c++ {
			// we don't need to visit cell twice
			if visited[[2]int{r, c}] {
				continue
			}

			ncc := 0
			v := grid[r][c]

			s.Push(r, c)
			visited[[2]int{r, c}] = true

			for !s.IsEmpty() {

				for i := 0; i < 4; i++ {
					rn := r + dr[i]
					cn := c + dc[i]

					if rn < 0 || cn < 0 {
						continue
					}
					if rn >= rl || cn >= cl {
						continue
					}
					if grid[rn][cn] != v {
						continue
					}
					if visited[[2]int{rn, cn}] {
						continue
					}

					s.Push(rn, cn)
					visited[[2]int{rn, cn}] = true
				}

				r, c = s.Pop()
				ncc++
			}

			if result < ncc {
				result = ncc
			}
		}
	}

	return result
}

func Test_Find_max_number_of_connected_colors_in_grid (t *testing.T) {

	for _, td := range testDatas {
		r := Find_max_number_of_connected_colors_in_grid(td.grid)

		for td.result != r {
			t.Errorf("Grid:%v /n Expected: %d, Actual: %d",
				td.grid,
				td.result,
				r)
		}
	}
}

var testDatas = []struct{
	grid [][]int
	result int
}{
	{
		[][]int{
			{0, 1, 2, 1, },
			{0, 0, 2, 1, },
			{2, 2, 2, 1, },
			{1, 1, 1, 1, },
		},
		7,
	},
	{
		[][]int{
			{0, 0, 2, 1, },
			{0, 2, 1, 2, },
			{1, 2, 2, 2  },
		},
		5,
	},
	{
		[][]int{
			{0, 0, 0, 0, },
			{0, 0, 0, 0, },
			{0, 0, 0, 0, },
			{0, 0, 0, 0, },
		},
		16,
	},
	{
		[][]int{
			{0,},
		},
		1,
	},
	{
		[][]int{},
		0,
	},
}