package main import ( "fmt" "math" "strconv" "strings" ) func main() { var h, w int _, _ = fmt.Scan(&h, &w) total := 0 line := "" paint := make([]int, h*w) black := make([]int, 0) for i := 0; i < h; i++ { _, _ = fmt.Scan(&line) for j, c := range line { if string(c) == "#" { total++ paint[i*w+j] = 1 black = append(black, i*w+j) } } } if total%2 != 0 { fmt.Println("NO") return } // 半分を塗って、塗った部分を全部同じ数だけシフトして移動可能なら成功 start, goal := int(math.Pow(2, float64(total))), int(math.Pow(2, float64(total-1))) for i := start; i > goal; i-- { // 塗る場所の取得 fill := fmt.Sprintf("%0"+strconv.Itoa(total)+"b", i) if strings.Count(fill, "1") != total/2 { continue } src := make([]int, 0) dst := make([]int, 0) for i, b := range fill { if string(b) == "1" { src = append(src, black[i]) } else { dst = append(dst, black[i]) } if len(src) < len(dst) { break } } if len(src) != len(dst) { continue } // fmt.Println(fill, src, dst) // 先頭からすべて同じ移動量で実現するかのチェック r := true s := dst[0] - src[0] // 移動量 if s < 1 { // 左上から右か下か右下へのシフトのみを試せばいいので、移動量が0以下はスキップ continue } for j := 1; j < len(src); j++ { if src[j]+s != dst[j] { r = false break } } if r { fmt.Println("YES") return } } fmt.Println("NO") }