fork(1) download
  1. stk=input().split()
  2. n=int(stk[0]);m=int(stk[1]);k=int(stk[2]);v=float(stk[3])
  3. bmap=[]
  4. for i in range(m): bmap.append(input())
  5. x0,y0 = [int(x) for x in input().split()]
  6. x0-=1
  7. y0-=1
  8. bombs=[]
  9. for i in range(k):
  10. stsss = input().split()
  11. bombs.append((int(stsss[0])-1, int(stsss[1])-1))
  12. vmin=10**10
  13. import math,copy
  14. d9dx = math.sqrt(2)
  15.  
  16. def dj(x,y,marks,d,kx,ky):
  17. marks[y][x]=True
  18. if kx==x and ky==y:
  19. global vmin
  20. vmin=min(vmin, d)
  21. for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:
  22. if x+dx>=0 and y+dy>=0 and x+dx<n and y+dy<m and not marks[y+dy][x+dx] and bmap[y+dy][x+dx]==".":
  23. dj(x+dx, y+dy, copy.copy(marks), d+1, kx,ky)
  24. global d9dx
  25. for dx,dy in [(1,1),(-1,1),(1,-1),(-1,-1)]:
  26. if x+dx>=0 and y+dy>=0 and x+dx<n and y+dy<m and not marks[y+dy][x+dx] and bmap[y+dy][x+dx]==".":
  27. dj(x+dx, y+dy, copy.copy(marks), d+d9dx, kx,ky)
  28.  
  29. sm=0
  30. for i in range(k):
  31. dj(x0,y0,[[False for j in range(n)] for x in range(m)],0,bombs[i][0], bombs[i][1])
  32. if vmin!=0:
  33. x0,y0 = bombs[i]
  34. sm+=vmin
  35. vmin=10**10
  36. sm/=v
  37. print("%.2f" % sm)
Success #stdin #stdout 0.01s 28384KB
stdin
4 3 3 1.23
....
##..
....
1 1
1 3
4 1
4 3
stdout
13.82