Advertisement
Egmell

5

Apr 18th, 2024
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Go 1.59 KB | None | 0 0
  1. package main
  2.  
  3. import (
  4.     "bufio"
  5.     "fmt"
  6.     "os"
  7.     "strconv"
  8.     "strings"
  9. )
  10.  
  11. func maxMushrooms(n int, forest [][]rune) int {
  12.     if n == 0 {
  13.         return 0
  14.     }
  15.  
  16.     dp := make([][]int, n)
  17.     for i := range dp {
  18.         dp[i] = []int{-1, -1, -1}
  19.     }
  20.  
  21.     countFirstBushes := 0
  22.     for j := 0; j < 3; j++ {
  23.         if forest[0][j] == 'C' {
  24.             dp[0][j] = 1
  25.         } else if forest[0][j] == 'W' {
  26.             countFirstBushes++
  27.         } else {
  28.             dp[0][j] = 0
  29.         }
  30.     }
  31.     if countFirstBushes == 3 {
  32.         return 0
  33.     }
  34.     i := 1
  35.     countImpossibleCells := 0
  36.     for ; i < n; i++ {
  37.         for j := 0; j < 3; j++ {
  38.             if forest[i][j] == 'W' {
  39.                 countImpossibleCells++
  40.                 continue
  41.             }
  42.             for k := -1; k <= 1; k++ {
  43.                 if j+k >= 0 && j+k < 3 && dp[i-1][j+k] > dp[i][j] {
  44.                     dp[i][j] = dp[i-1][j+k]
  45.                 }
  46.             }
  47.             if dp[i][j] == -1 {
  48.                 countImpossibleCells++
  49.                 continue
  50.             }
  51.             if forest[i][j] == 'C' {
  52.                 dp[i][j]++
  53.             }
  54.         }
  55.         if countImpossibleCells == 3 {
  56.             break
  57.         }
  58.         countImpossibleCells = 0
  59.     }
  60.  
  61.     maxMushrooms := 0
  62.     for j := 0; j < 3; j++ {
  63.         if dp[i-1][j] > maxMushrooms {
  64.             maxMushrooms = dp[i-1][j]
  65.         }
  66.     }
  67.  
  68.     return maxMushrooms
  69. }
  70.  
  71. func main() {
  72.     scanner := bufio.NewScanner(os.Stdin)
  73.     buf := make([]byte, 1e4)
  74.     scanner.Buffer(buf, 1e4)
  75.  
  76.     scanner.Scan()
  77.     n, _ := strconv.Atoi(strings.Split(scanner.Text(), " ")[0])
  78.  
  79.     forest := make([][]rune, n)
  80.     for i := range forest {
  81.         scanner.Scan()
  82.         fields := strings.Fields(scanner.Text())
  83.         forest[i] = make([]rune, 3)
  84.         for j := 0; j < len(fields[0]); j++ {
  85.             forest[i][j] = []rune(fields[0])[j]
  86.         }
  87.     }
  88.  
  89.     result := maxMushrooms(n, forest)
  90.     fmt.Println(result)
  91. }
  92.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement