leetcode-go/oj/hulu/path.go

package main

import "fmt"

var n, m int

var dy = [4]int{0, 1, 0, -1}
var dx = [4]int{1, 0, -1, 0}

func getArea(grid [][]int) int {
	queue := make([][2]int, 0)
	used := make([][]bool, n)
	for i := range used {
		used[i] = make([]bool, m)
	}
	y, x := 0, 0
	for i := 0; i < 4; i++ {
		l := m - 1
		if i&1 == 1 {
			l = n - 1
		}
		for j := 0; j < l; j++ {
			if grid[y][x] == 0 {
				queue = append(queue, [2]int{y, x})
				used[y][x] = true
			}
			y, x = y+dy[i], x+dx[i]
		}
	}
	area, size := len(queue), len(queue)
	for size != 0 {
		pos := queue[0]
		queue = queue[1:]
		size--
		for i := 0; i < 4; i++ {
			ny, nx := pos[0]+dy[i], pos[1]+dx[i]
			if ny < 0 || n <= ny || nx < 0 || m <= nx || grid[ny][nx] == 1 || used[ny][nx] {
				continue
			}
			queue = append(queue, [2]int{ny, nx})
			used[ny][nx] = true
		}
		if size == 0 {
			size = len(queue)
			area += size
		}
	}
	return n*m - area
}

func main() {
	fmt.Scan(&n, &m)
	grid := make([][]int, n)
	for i := range grid {
		grid[i] = make([]int, m)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			fmt.Scan(&grid[i][j])
		}
	}
	fmt.Println(getArea(grid))
}