Mischievous Shooter (Codeforces 1921G)
Tags: Implement, divide and conquer

Once the mischievous and wayward shooter named Shel found himself on a rectangular field of size $$$n \times m$$$, divided into unit squares. Each cell either contains a target or not.Shel only had a lucky shotgun with him, with which he can shoot in one of the four directions: right-down, left-down, left-up, or right-up. When fired, the shotgun hits all targets in the chosen direction, the Manhattan distance to which does not exceed a fixed constant $$$k$$$. The Manhattan distance between two points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is equal to $$$|x_1 - x_2| + |y_1 - y_2|$$$.  Possible hit areas for $$$k = 3$$$. Shel's goal is to hit as many targets as possible. Please help him find this value.

Input: Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Then follows the description of the test cases.The first line of each test case contains field dimensions $$$n$$$, $$$m$$$, and the constant for the shotgun's power $$$k$$$ ($$$1 \le n, m, k \le 10^5, 1 \le n \cdot m \le 10^5$$$).Each of the next $$$n$$$ lines contains $$$m$$$ characters — the description of the next field row, where the character '.' means the cell is empty, and the character '#' indicates the presence of a target. It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, output a single integer on a separate line, which is equal to the maximum possible number of hit targets with one shot.

Note: Possible optimal shots for the examples in the statement:  

Sample Inputs:
4
3 3 1
.#.
###
.#.
2 5 3
###..
...##
4 4 2
..##
###.
#..#
####
2 1 3
#
#

Sample Outputs:
3
4
5
2

Solution (Python):
def make2DRangeSumQuery(arr2D):
    (n, m) = (len(arr2D), len(arr2D[0]))
    (N, M) = (n + 1, m + 1)
    p = [0] * (N * M)
    for i in range(n):
        for j in range(m):
            p[(i + 1) * M + j + 1] = arr2D[i][j]
    for i in range(N):
        for j in range(1, M):
            p[i * M + j] += p[i * M + j - 1]
    for i in range(1, N):
        for j in range(M):
            p[i * M + j] += p[(i - 1) * M + j]

    def querySum(i1, j1, i2, j2):
        if i1 > i2:
            (i1, i2) = (i2, i1)
        if j1 > j2:
            (j1, j2) = (j2, j1)
        return p[(i2 + 1) * M + j2 + 1] - p[(i2 + 1) * M + j1] - p[i1 * M + j2 + 1] + p[i1 * M + j1]
    return querySum

def printgrid(arr):
    for row in arr:
        print(row)
    return

def cw90Rotate(arr2d):
    n = len(arr2d)
    m = len(arr2d[0])
    arrOut = [[None for _ in range(n)] for __ in range(m)]
    for i in range(m):
        for j in range(n):
            arrOut[i][j] = arr2d[n - 1 - j][i]
    return arrOut

def solve(n, m, k, grid):
    diag_range_sum_arr = [[0 for _ in range(m)] for __ in range(n)]
    for i in range(n):
        for j in range(m):
            if grid[i][j] == '#':
                diag_range_sum_arr[i][j] += 1
            if i - 1 >= 0 and j - 1 >= 0:
                diag_range_sum_arr[i][j] += diag_range_sum_arr[i - 1][j - 1]

    def query_diag(i, j, L):
        ans = diag_range_sum_arr[i][j]
        if i - L >= 0 and j - L >= 0:
            ans -= diag_range_sum_arr[i - L][j - L]
        return ans
    arr = [[0 for _ in range(m)] for __ in range(n)]
    for i in range(n):
        for j in range(m):
            if grid[i][j] == '#':
                arr[i][j] = 1
    query_sum = make2DRangeSumQuery(arr)
    dp = [[0 for _ in range(m)] for __ in range(n)]
    for j in range(k + 1):
        if j == m:
            break
        if grid[0][j] == '#':
            dp[0][0] += 1
    for i in range(1, n):
        dp[i][0] += dp[i - 1][0]
        dp[i][0] += query_sum(i, 0, i, min(k, m - 1))
        i2 = i - 1
        j2 = k
        d = k + 1
        if j2 >= m:
            d -= j2 - (m - 1)
            i2 -= j2 - (m - 1)
            j2 = m - 1
        if i2 >= 0:
            dp[i][0] -= query_diag(i2, j2, d)
    for i in range(n):
        for j in range(1, m):
            dp[i][j] += dp[i][j - 1]
            i2 = i
            j2 = j + k
            d = k + 1
            if j2 >= m:
                d -= j2 - (m - 1)
                i2 -= j2 - (m - 1)
                j2 = m - 1
            if i2 >= 0:
                dp[i][j] += query_diag(i2, j2, d)
            dp[i][j] -= query_sum(max(0, i - k), j - 1, i, j - 1)
    ans = 0
    for i in range(n):
        for j in range(m):
            ans = max(ans, dp[i][j])
    return ans

def test():
    k = 2
    grid = ['....', '.#..', '.##.', '.###', '....']
    (n, m) = (len(grid), len(grid[0]))
    solve(n, m, k, grid)
    dp = [[0 for _ in range(m)] for __ in range(n)]
    for i in range(n):
        for j in range(m):
            i3 = i - k
            for d in range(k + 1):
                i2 = i3 + d
                for j2 in range(j, j + d + 1):
                    if 0 <= i2 < n and 0 <= j2 < m and (grid[i2][j2] == '#'):
                        dp[i][j] += 1
    print()
    printgrid(dp)
    return

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        (n, m, k) = readIntArr()
        grid = []
        for __ in range(n):
            grid.append(input())
        ans = 0
        for z in range(4):
            ans = max(ans, solve(len(grid), len(grid[0]), k, grid))
            if z != 3:
                grid = cw90Rotate(grid)
        allans.append(ans)
    multiLineArrayPrint(allans)
    return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())

def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
import sys
dir = ((1, 1), (1, -1), (-1, 1), (-1, -1))
num = int(input())
for _ in range(num):
    (n, m, k) = map(int, input().split())
    grid = [list(input()) for _ in range(n)]
    if n > m:
        grid = list(zip(*grid))
        (n, m) = (m, n)
    prefix = [[0] * (m + 1) for _ in range(n)]
    for i in range(n):
        for j in range(m):
            prefix[i][j + 1] = prefix[i][j] + int(grid[i][j] == '#')
    result = 0
    for i in range(n):
        for j in range(m):
            for (di, dj) in dir:
                curr = 0
                for l in range(k + 1):
                    ni = i + l * di
                    if not 0 <= ni < n:
                        break
                    (src, dst) = (j, j + (k - l) * dj)
                    if src > dst:
                        (src, dst) = (dst, src)
                    curr += prefix[ni][min(dst, m - 1) + 1] - prefix[ni][max(src, 0)]
                result = max(result, curr)
    print(result)

Solution (Python):
import copy
from copy import deepcopy

def Calc(n, m, k, S):
    Tilt = deepcopy(S)
    for i in range(1, n):
        for j in range(1, m):
            Tilt[i][j] += Tilt[i - 1][j - 1]
    res = 0
    F = [0] * m
    for i in range(n):
        Pre = [S[i][0]]
        for j in range(1, m):
            Pre.append(Pre[j - 1] + S[i][j])
        for j in range(m):
            x = j + k
            F[j] += Pre[min(x, m - 1)] - (0 if j == 0 else Pre[j - 1])
            if i - x + m > 1 and i > 0:
                F[j] -= (Tilt[i - 1][x] if x < m else Tilt[i - 2 - x + m][m - 1]) - (0 if j == 0 or i - k < 2 else Tilt[i - k - 2][j - 1])
            res = max(res, F[j])
    return res

def Rev(n, S):
    for i in range(n):
        S[i].reverse()
    return S

def Solve():
    num = input().split()
    n = int(num[0])
    m = int(num[1])
    k = int(num[2])
    S = []
    for i in range(n):
        S.append(input())
    Trans = lambda x: 1 if x == '#' else 0
    S = [[Trans(x) for x in L] for L in S]
    ans = Calc(n, m, k, S)
    S = Rev(n, S)
    ans = max(ans, Calc(n, m, k, S))
    for i in range(n // 2):
        for j in range(m):
            x = S[i][j]
            S[i][j] = S[n - i - 1][j]
            S[n - i - 1][j] = x
    ans = max(ans, Calc(n, m, k, S))
    Rev(n, S)
    print(max(ans, Calc(n, m, k, S)))
t = int(input())
for i in range(0, t):
    Solve()