Rarity and New Dress (Codeforces 1393D)
Tags: DP, shortest paths

Carousel Boutique is busy again! Rarity has decided to visit the pony ball and she surely needs a new dress, because going out in the same dress several times is a sign of bad manners. First of all, she needs a dress pattern, which she is going to cut out from the rectangular piece of the multicolored fabric.The piece of the multicolored fabric consists of $$$n \times m$$$ separate square scraps. Since Rarity likes dresses in style, a dress pattern must only include scraps sharing the same color. A dress pattern must be the square, and since Rarity is fond of rhombuses, the sides of a pattern must form a $$$45^{\circ}$$$ angle with sides of a piece of fabric (that way it will be resembling the traditional picture of a rhombus).Examples of proper dress patterns:  Examples of improper dress patterns:  The first one consists of multi-colored scraps, the second one goes beyond the bounds of the piece of fabric, the third one is not a square with sides forming a $$$45^{\circ}$$$ angle with sides of the piece of fabric.Rarity wonders how many ways to cut out a dress pattern that satisfies all the conditions that do exist. Please help her and satisfy her curiosity so she can continue working on her new masterpiece!

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2000$$$). Each of the next $$$n$$$ lines contains $$$m$$$ characters: lowercase English letters, the $$$j$$$-th of which corresponds to scrap in the current line and in the $$$j$$$-th column. Scraps having the same letter share the same color, scraps having different letters have different colors.

Output: Print a single integer: the number of ways to cut out a dress pattern to satisfy all of Rarity's conditions.

Note: In the first example, all the dress patterns of size $$$1$$$ and one of size $$$2$$$ are satisfactory.In the second example, only the dress patterns of size $$$1$$$ are satisfactory.

Sample Inputs:
3 3
aaa
aaa
aaa

3 4
abab
baba
abab

5 5
zbacg
baaac
aaaaa
eaaad
weadd

Sample Outputs:
10

12

31

Solution (Python):
import io
import os
from array import array
ordA = ord('a')

def solve(R, C, grid):
    seen = [False for i in range(26)]
    for i in range(R * C):
        seen[grid[i] - ordA] = True
    ans = 0
    CC = C + 1
    dp2 = array('h', (0 for i in range(CC)))
    dp1 = array('h', (0 for i in range(CC)))
    dp0 = array('h', (0 for i in range(CC)))
    for i in range(26):
        ch = ordA + i
        if seen[i]:
            for c in range(C):
                dp2[c] = 0
                dp1[c] = 0
            j = 0
            for r in range(R):
                for c in range(C):
                    dp0[c] = 0 if grid[j] != ch else 1 + min(dp2[c], dp1[c - 1], dp1[c], dp1[c + 1])
                    ans += dp0[c]
                    j += 1
                (dp2, dp1, dp0) = (dp1, dp0, dp2)
    return ans

def solve(R, C, grid):
    ans = 0
    CC = C + 1
    dp2 = array('h', (0 for i in range(CC)))
    dp1 = array('h', (0 for i in range(CC)))
    dp0 = array('h', (0 for i in range(CC)))
    for r in range(R):
        for c in range(C):
            ch = grid[r * C + c]
            dp0[c] = 1
            if r >= 2 and 0 < c < C - 1 and (grid[(r - 2) * C + c] == grid[(r - 1) * C + c - 1] == grid[(r - 1) * C + c] == grid[(r - 1) * C + c + 1] == ch):
                dp0[c] = 1 + min(dp2[c], dp1[c - 1], dp1[c], dp1[c + 1])
            ans += dp0[c]
        (dp2, dp1, dp0) = (dp1, dp0, dp2)
    return ans
if __name__ == '__main__':
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
    (N, M) = [int(x) for x in input().split()]
    grid = b''.join((input().rstrip() for i in range(N)))
    ans = solve(N, M, grid)
    print(ans)

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
import threading
from collections import defaultdict
import heapq
from math import ceil, floor

def main():
    ans = 0
    (n, m) = map(int, input().split())
    dp = [[0] * m for i in range(n)]
    ans = 0
    s = []
    for i in range(n):
        s.append(input())
        for j in range(m):
            dp[i][j] = 1
            if i >= 2 and 0 < j < m - 1:
                if s[i][j] == s[i - 1][j - 1] == s[i - 1][j + 1] == s[i - 2][j] == s[i - 1][j]:
                    dp[i][j] += min(dp[i - 1][j - 1], dp[i - 1][j + 1], dp[i - 2][j])
            ans += dp[i][j]
    print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    for i in range(1):
        main()

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
dp1 = []
dp0 = [0] * m
s = []
s0 = [0] * m
for i in range(n):
    dp = [0] * m
    s1 = list(input().rstrip())
    (c, w) = (0, s1[0])
    for j in range(m):
        if s1[j] ^ w:
            w = s1[j]
            c = 0
        c += 1
        dp[j] = c
    (c, w) = (0, s1[-1])
    for j in range(m - 1, -1, -1):
        if s1[j] ^ w:
            w = s1[j]
            c = 0
        c += 1
        if s0[j] ^ s1[j]:
            dp[j] = 1
        else:
            dp[j] = min(dp[j], c, dp0[j] + 1)
    dp1.append(list(dp))
    dp0 = dp
    s.append(list(s1))
    s0 = s1
dp0 = [0] * m
s0 = [0] * m
ans = 0
for i in range(n - 1, -1, -1):
    dp = [0] * m
    s1 = s[i]
    (c, w) = (0, s1[0])
    for j in range(m):
        if s1[j] ^ w:
            w = s1[j]
            c = 0
        c += 1
        dp[j] = c
    (c, w) = (0, s1[-1])
    for j in range(m - 1, -1, -1):
        if s1[j] ^ w:
            w = s1[j]
            c = 0
        c += 1
        if s0[j] ^ s1[j]:
            dp[j] = 1
        else:
            dp[j] = min(dp[j], c, dp0[j] + 1)
    for (j, k) in zip(dp, dp1[i]):
        ans += min(j, k)
    dp0 = dp
    s0 = s1
print(ans)