Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package main
- import (
- "bufio"
- "fmt"
- "os"
- "strconv"
- "strings"
- )
- func maxMushrooms(n int, forest [][]rune) int {
- if n == 0 {
- return 0
- }
- dp := make([][]int, n)
- for i := range dp {
- dp[i] = []int{-1, -1, -1}
- }
- countFirstBushes := 0
- for j := 0; j < 3; j++ {
- if forest[0][j] == 'C' {
- dp[0][j] = 1
- } else if forest[0][j] == 'W' {
- countFirstBushes++
- } else {
- dp[0][j] = 0
- }
- }
- if countFirstBushes == 3 {
- return 0
- }
- i := 1
- countImpossibleCells := 0
- for ; i < n; i++ {
- for j := 0; j < 3; j++ {
- if forest[i][j] == 'W' {
- countImpossibleCells++
- continue
- }
- for k := -1; k <= 1; k++ {
- if j+k >= 0 && j+k < 3 && dp[i-1][j+k] > dp[i][j] {
- dp[i][j] = dp[i-1][j+k]
- }
- }
- if dp[i][j] == -1 {
- countImpossibleCells++
- continue
- }
- if forest[i][j] == 'C' {
- dp[i][j]++
- }
- }
- if countImpossibleCells == 3 {
- break
- }
- countImpossibleCells = 0
- }
- maxMushrooms := 0
- for j := 0; j < 3; j++ {
- if dp[i-1][j] > maxMushrooms {
- maxMushrooms = dp[i-1][j]
- }
- }
- return maxMushrooms
- }
- func main() {
- scanner := bufio.NewScanner(os.Stdin)
- buf := make([]byte, 1e4)
- scanner.Buffer(buf, 1e4)
- scanner.Scan()
- n, _ := strconv.Atoi(strings.Split(scanner.Text(), " ")[0])
- forest := make([][]rune, n)
- for i := range forest {
- scanner.Scan()
- fields := strings.Fields(scanner.Text())
- forest[i] = make([]rune, 3)
- for j := 0; j < len(fields[0]); j++ {
- forest[i][j] = []rune(fields[0])[j]
- }
- }
- result := maxMushrooms(n, forest)
- fmt.Println(result)
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement