package main

import (
	"fmt"
	"os"
	"strings"
)

type Pair struct {
	r, c int
}

func readInput() []string {
	data, _ := os.ReadFile("input.txt")
	content := strings.TrimSpace(string(data))
	lines := strings.Split(strings.ReplaceAll(string(content), "\r\n", "\n"), "\n")

	return lines
}

func part1() {
	lines := readInput()
	size := len(lines[0])
	prev := []bool{}
	for i := range size {
		prev = append(prev, lines[0][i] == 'S')
	}
	result := 0
	for _, line := range lines[1:] {
		curr := make([]bool, size)
		count := 0
		for i := range size {
			if prev[i] {
				if line[i] == '^' {
					if i-1 >= 0 {
						curr[i-1] = true
					}
					if i+1 < size {
						curr[i+1] = true
					}
					count++
				} else {
					curr[i] = true
				}
			}
		}
		// fmt.Println(count)
		result += count
		prev = curr
	}

	fmt.Printf("%d\n", result)
}

func part2() {
	lines := readInput()
	w, h := len(lines[0]), len(lines)
	cache := make(map[Pair]int)
	var count func(r, c int) int
	count = func(r, c int) int {
		if c < 0 || c >= w {
			return 0
		}
		if r == h {
			return 1
		}
		if _, ok := cache[Pair{r, c}]; ok {
			return cache[Pair{r, c}]
		}
		if lines[r][c] == '^' {
			result := count(r+1, c-1) + count(r+1, c+1)
			cache[Pair{r, c}] = result
			return result
		}
		result := count(r+1, c)
		cache[Pair{r, c}] = result
		return result
	}
	r0, c0 := 0, strings.IndexByte(lines[0], 'S')
	result := count(r0, c0)

	fmt.Printf("%d\n", result)
}

func main() {
	part1()
	part2()
}