Mr K marsh
程序员文章站
2022-04-29 09:00:45
...
暴力思路,然后为了去掉一些重复运算,做下面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.'])