Submission #1680351

---

Source Code Expand

package main

import (
	"fmt"
)

func main() {
	var H, W int
	fmt.Scan(&H, &W)
	c := make([]string, H)
	for i := 0; i < H; i++ {
		fmt.Scan(&c[i])
	}
	var ma [310][310]int
	var dp [310][310]int
	var ans int
	for n := 0; n < W-1; n++ {
		for i := 0; i < H; i++ {
			for j := 0; j < H; j++ {
				if c[i][n] == c[j][n+1] {
					ma[i+1][j+1] = ma[i][j] + 1
				} else {
					ma[i+1][j+1] = ma[i][j]
				}
			}
		}
		for i := 0; i < H; i++ {
			for j := 0; j < H; j++ {
				dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j]) + ma[i+1][j+1]
			}
		}
		ans += dp[H][H]
	}
	fmt.Println(ans)
}

func min(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r > a[i] {
			r = a[i]
		}
	}
	return r
}

Submission Info

Judge Result