欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Mr K marsh

程序员文章站 2022-04-29 09:00:45
...

Mr K marsh

Mr K marsh

暴力思路,然后为了去掉一些重复运算,做下面2个优化

1. 先用4个DP数组表示当前位置能往上下左右expand的长度

2. 循环的时候,如果当前循环最大也不比当前的最好大,就可直接break

def kMarsh(grid):
    n,m=len(grid),len(grid[0])
    up=[[0 for _ in range(m)] for _ in range(n)]
    down=[[0 for _ in range(m)] for _ in range(n)]
    left=[[0 for _ in range(m)] for _ in range(n)]
    right=[[0 for _ in range(m)] for _ in range(n)]
    
    for i in range(n):
        s=0
        for j in range(m):
            if grid[i][j]=='.': s+=1
            else: s=0
            left[i][j]=s
    for i in range(n):
        s=0
        for j in range(m-1,-1,-1):
            if grid[i][j]=='.': s+=1
            else: s=0
            right[i][j]=s  
    for j in range(m):
        s=0
        for i in range(n):
            if grid[i][j]=='.': s+=1
            else: s=0
            up[i][j]=s
    for j in range(m):
        s=0
        for i in range(n-1,-1,-1):
            if grid[i][j]=='.': s+=1
            else: s=0
            down[i][j]=s
    
#    s=set()
    
#    print(up)
#    print(down)
#    print(left)
#    print(right)
    
    ma = 0
    for i in range(n):
        for j in range(m):
            if grid[i][j]=='x': continue
            if 2*(down[i][j]-1+right[i][j]-1)<=ma: break
            for p in range(i+down[i][j]-1, i, -1):
                if 2*(p-i+right[i][j]-1)<=ma: break
                for q in range(j+right[i][j]-1, j, -1):
                    if grid[p][q]=='x': continue
                    if 2*(p-i+q-j)<=ma: break
                    if p-up[p][q]+1<=i and q-left[p][q]+1<=j:
                        ma = max(ma, 2*(p-i+q-j))
                        break
    print(ma if ma else 'impossible')


kMarsh(['.....','.x.x.','.....','.....'])
kMarsh(['.....','xxxx.'])