h, w = list(map(int, input().split()))

lst = [['*' for i in range(w+2)]]

for i in range(h):

    string = eval(input())

    lsti = ['*']

    for j in range(w):

        lsti.append(string[j])

        if string[j] == 's':

            start = (i+1, j+1)

        elif string[j] == 'g':

            goal = (i+1, j+1)

    lsti.append('*')

    lst.append(lsti)

lst.append(['*' for i in range(w+2)])



lst_cnt = [[300 for i in range(w+2)] for j in range(h+2)]

if lst[1][1] == '#':

    lst_cnt[1][1] = -1

else:

    lst_cnt[1][1] = 0



queue_new = [(1, 1)]

while queue_new != []:

    queue = queue_new

    queue_new = []

    while queue != []:

        zahyo = queue.pop()

        i, j = zahyo[0], zahyo[1]

        if lst[i+1][j] == '#':

            if lst_cnt[i][j] < 0:

                if abs(lst_cnt[i][j]) < abs(lst_cnt[i+1][j]):

                    lst_cnt[i+1][j] = -abs(lst_cnt[i][j])

                    queue_new.append((i+1, j))

            else:

                if abs(lst_cnt[i][j])+1 < abs(lst_cnt[i+1][j]):

                    lst_cnt[i+1][j] = -(abs(lst_cnt[i][j])+1)

                    queue_new.append((i+1, j))

        elif lst[i+1][j] == '.':

            if abs(lst_cnt[i][j]) < abs(lst_cnt[i+1][j]):

                lst_cnt[i+1][j] = abs(lst_cnt[i][j])

                queue_new.append((i+1, j))

        

        if lst[i][j+1] == '#':

            if lst_cnt[i][j] < 0:

                if abs(lst_cnt[i][j]) < abs(lst_cnt[i][j+1]):

                    lst_cnt[i][j+1] = -abs(lst_cnt[i][j])

                    queue_new.append((i, j+1))

            else:

                if abs(lst_cnt[i][j])+1 < abs(lst_cnt[i][j+1]):

                    lst_cnt[i][j+1] = -(abs(lst_cnt[i][j])+1)

                    queue_new.append((i, j+1))

        elif lst[i][j+1] == '.':

            if abs(lst_cnt[i][j]) < abs(lst_cnt[i][j+1]):

                lst_cnt[i][j+1] = abs(lst_cnt[i][j])

                queue_new.append((i, j+1))

print((abs(lst_cnt[h][w])))
h, w = list(map(int, input().split()))

lst = [['*' for i in range(w+2)]]

for i in range(h):

    lsti = ['*']

    lsti.extend(list(eval(input())))

    lsti.append('*')

    lst.append(lsti)

lst.append(['*' for i in range(w+2)])



lst_cnt = [[300 for i in range(w+2)] for j in range(h+2)]

if lst[1][1] == '#': lst_cnt[1][1] = -1

else: lst_cnt[1][1] = 0



for i in range(1, h+1):

    for j in range(1, w+1):

        if i == 1 and j == 1: continue

        if lst[i][j] == '.':

            lst_cnt[i][j] = min(abs(lst_cnt[i-1][j]), abs(lst_cnt[i][j-1]))

        else:

            if lst[i-1][j] == '#':

                kouho1 = lst_cnt[i-1][j]

            else:

                kouho1 = -(lst_cnt[i-1][j]+1)

            if lst[i][j-1] == '#':

                kouho2 = lst_cnt[i][j-1]

            else:

                kouho2 = -(lst_cnt[i][j-1]+1)

            lst_cnt[i][j] = -min(abs(kouho1), abs(kouho2))



print((abs(lst_cnt[h][w])))
h, w = list(map(int, input().split()))
lst = [["*" for i in range(w + 2)]]
for i in range(h):
    string = eval(input())
    lsti = ["*"]
    for j in range(w):
        lsti.append(string[j])
        if string[j] == "s":
            start = (i + 1, j + 1)
        elif string[j] == "g":
            goal = (i + 1, j + 1)
    lsti.append("*")
    lst.append(lsti)
lst.append(["*" for i in range(w + 2)])
lst_cnt = [[300 for i in range(w + 2)] for j in range(h + 2)]
if lst[1][1] == "#":
    lst_cnt[1][1] = -1
else:
    lst_cnt[1][1] = 0
queue_new = [(1, 1)]
while queue_new != []:
    queue = queue_new
    queue_new = []
    while queue != []:
        zahyo = queue.pop()
        i, j = zahyo[0], zahyo[1]
        if lst[i + 1][j] == "#":
            if lst_cnt[i][j] < 0:
                if abs(lst_cnt[i][j]) < abs(lst_cnt[i + 1][j]):
                    lst_cnt[i + 1][j] = -abs(lst_cnt[i][j])
                    queue_new.append((i + 1, j))
            else:
                if abs(lst_cnt[i][j]) + 1 < abs(lst_cnt[i + 1][j]):
                    lst_cnt[i + 1][j] = -(abs(lst_cnt[i][j]) + 1)
                    queue_new.append((i + 1, j))
        elif lst[i + 1][j] == ".":
            if abs(lst_cnt[i][j]) < abs(lst_cnt[i + 1][j]):
                lst_cnt[i + 1][j] = abs(lst_cnt[i][j])
                queue_new.append((i + 1, j))
        if lst[i][j + 1] == "#":
            if lst_cnt[i][j] < 0:
                if abs(lst_cnt[i][j]) < abs(lst_cnt[i][j + 1]):
                    lst_cnt[i][j + 1] = -abs(lst_cnt[i][j])
                    queue_new.append((i, j + 1))
            else:
                if abs(lst_cnt[i][j]) + 1 < abs(lst_cnt[i][j + 1]):
                    lst_cnt[i][j + 1] = -(abs(lst_cnt[i][j]) + 1)
                    queue_new.append((i, j + 1))
        elif lst[i][j + 1] == ".":
            if abs(lst_cnt[i][j]) < abs(lst_cnt[i][j + 1]):
                lst_cnt[i][j + 1] = abs(lst_cnt[i][j])
                queue_new.append((i, j + 1))
print((abs(lst_cnt[h][w])))

h, w = list(map(int, input().split()))
lst = [["*" for i in range(w + 2)]]
for i in range(h):
    lsti = ["*"]
    lsti.extend(list(eval(input())))
    lsti.append("*")
    lst.append(lsti)
lst.append(["*" for i in range(w + 2)])
lst_cnt = [[300 for i in range(w + 2)] for j in range(h + 2)]
if lst[1][1] == "#":
    lst_cnt[1][1] = -1
else:
    lst_cnt[1][1] = 0
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if i == 1 and j == 1:
            continue
        if lst[i][j] == ".":
            lst_cnt[i][j] = min(abs(lst_cnt[i - 1][j]), abs(lst_cnt[i][j - 1]))
        else:
            if lst[i - 1][j] == "#":
                kouho1 = lst_cnt[i - 1][j]
            else:
                kouho1 = -(lst_cnt[i - 1][j] + 1)
            if lst[i][j - 1] == "#":
                kouho2 = lst_cnt[i][j - 1]
            else:
                kouho2 = -(lst_cnt[i][j - 1] + 1)
            lst_cnt[i][j] = -min(abs(kouho1), abs(kouho2))
print((abs(lst_cnt[h][w])))

-    string = eval(input()) -    for j in range(w): -        lsti.append(string[j]) -        if string[j] == "s": -            start = (i + 1, j + 1) -        elif string[j] == "g": -            goal = (i + 1, j + 1) +    lsti.extend(list(eval(input()))) -queue_new = [(1, 1)] -while queue_new != []: -    queue = queue_new -    queue_new = [] -    while queue != []: -        zahyo = queue.pop() -        i, j = zahyo[0], zahyo[1] -        if lst[i + 1][j] == "#": -            if lst_cnt[i][j] < 0: -                if abs(lst_cnt[i][j]) < abs(lst_cnt[i + 1][j]): -                    lst_cnt[i + 1][j] = -abs(lst_cnt[i][j]) -                    queue_new.append((i + 1, j)) +for i in range(1, h + 1): +    for j in range(1, w + 1): +        if i == 1 and j == 1: +            continue +        if lst[i][j] == ".": +            lst_cnt[i][j] = min(abs(lst_cnt[i - 1][j]), abs(lst_cnt[i][j - 1])) +        else: +            if lst[i - 1][j] == "#": +                kouho1 = lst_cnt[i - 1][j] -                if abs(lst_cnt[i][j]) + 1 < abs(lst_cnt[i + 1][j]): -                    lst_cnt[i + 1][j] = -(abs(lst_cnt[i][j]) + 1) -                    queue_new.append((i + 1, j)) -        elif lst[i + 1][j] == ".": -            if abs(lst_cnt[i][j]) < abs(lst_cnt[i + 1][j]): -                lst_cnt[i + 1][j] = abs(lst_cnt[i][j]) -                queue_new.append((i + 1, j)) -        if lst[i][j + 1] == "#": -            if lst_cnt[i][j] < 0: -                if abs(lst_cnt[i][j]) < abs(lst_cnt[i][j + 1]): -                    lst_cnt[i][j + 1] = -abs(lst_cnt[i][j]) -                    queue_new.append((i, j + 1)) +                kouho1 = -(lst_cnt[i - 1][j] + 1) +            if lst[i][j - 1] == "#": +                kouho2 = lst_cnt[i][j - 1] -                if abs(lst_cnt[i][j]) + 1 < abs(lst_cnt[i][j + 1]): -                    lst_cnt[i][j + 1] = -(abs(lst_cnt[i][j]) + 1) -                    queue_new.append((i, j + 1)) -        elif lst[i][j + 1] == ".": -            if abs(lst_cnt[i][j]) < abs(lst_cnt[i][j + 1]): -                lst_cnt[i][j + 1] = abs(lst_cnt[i][j]) -                queue_new.append((i, j + 1)) +                kouho2 = -(lst_cnt[i][j - 1] + 1) +            lst_cnt[i][j] = -min(abs(kouho1), abs(kouho2))