Problem:


Score: 400 points

Problem statement

We have an H \times W grid whose squares are painted black or white. The square at the i-th row from the top and the j-th column from the left is denoted as (i, j).

Snuke would like to play the following game on this grid. At the beginning of the game, there is a character called Kenus at square (1, 1). The player repeatedly moves Kenus up, down, left or right by one square. The game is completed when Kenus reaches square (H, W) passing only white squares.

Before Snuke starts the game, he can change the color of some of the white squares to black. However, he cannot change the color of square (1, 1) and (H, W). Also, changes of color must all be carried out before the beginning of the game.

When the game is completed, Snuke's score will be the number of times he changed the color of a square before the beginning of the game. Find the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed, that is, Kenus can never reach square (H, W) regardless of how Snuke changes the color of the squares.  

The color of the squares are given to you as characters s_{i, j}. If square (i, j) is initially painted by white, s_{i, j} is .; if square (i, j) is initially painted by black, s_{i, j} is #.

Constraints

H is an integer between 2 and 50 (inclusive).

W is an integer between 2 and 50 (inclusive).

s_{i, j} is . or # (1 \leq i \leq H, 1 \leq j \leq W).

s_{1, 1} and s_{H, W} are ..

Input

Input is given from Standard Input in the following format:

H W
s_{1, 1}s_{1, 2}s_{1, 3} ... s_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3} ... s_{2, W}
 :   :
s_{H, 1}s_{H, 2}s_{H, 3} ... s_{H, W}

Output

Print the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed.

Sample Input 1

3 3
..#
#..
...

Sample Output 1

2

The score 2 can be achieved by changing the color of squares as follows:

Sample Input 2

10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................

Sample Output 2

209



Sample input:
3 3
..#
#..
...


Sample output:
2

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import heapq
import copy
import itertools

inf = float('inf')
a = '.'
b = '#'

class Graph_dijkstra(object):
    def __init__(self, V: "List[int]", E: "Set[Tuple[Tuple, Tuple]]", L: "Dict[Tuple[Tuple, Tuple], int]"):
        self.V = V
        self.E = E
        self.L = L
        self.adjacent = self.init_adjacent() # type: Dict[int: List[int]]
        self.shortest_path = self.init_shortest_path() # type: Dict[FrozenSet[int, int], int]
    
    def init_adjacent(self):
        ret = {v: [] for v in self.V}
        for e in self.E:
            ret[e[0]].append(e[1])
        return ret
    
    def init_shortest_path(self):
        ret = {(s, g): inf for s, g in itertools.permutations(self.V, 2)}
        for v in self.V:
            ret[(v, v)] = 0
        return ret
    
    def dijkstra(self, s: int):
        D = {v: inf for v in self.V}
        D[s] = 0
        prev = {v: None for v in self.V}
        Q = [(0, s)]

        while len(Q) > 0:
            du, u = heapq.heappop(Q)
            for v in self.adjacent[u]:
                e = (u, v)
                alt = du + self.L[e]
                if alt < D[v]:
                    D[v] = alt
                    prev[v] = u
                    heapq.heappush(Q, (D[v], v))

        for v in self.V:
            self.shortest_path[(s, v)] = D[v]

    def find_shortest_path(self, s: int, g:int):
        d = self.shortest_path[(s, g)]
        if d < inf:
            return d
        self.dijkstra(s)
        return self.shortest_path[(s, g)]


def solve(H, W, s):
    V = []
    E = set()
    L = dict()
    direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    field = [[b for w in range(W+2)] for h in range(H+2)]
    white_count = 0
    for h in range(H):
        field[1+h][1:W+1] = s[h]
    for h in range(H):
        for w in range(W):
            if field[1+h][1+w] == b:
                continue
            V.append((1+h, 1+w))
            white_count += 1
            for d in direction:
                if field[1+h+d[0]][1+w+d[1]] == b:
                    continue
                e = ((1+h, 1+w), (1+h+d[0], 1+w+d[1]))
                E.add(e)
                L[e] = 1
    G = Graph_dijkstra(V, E, L)
    path_length = G.find_shortest_path((1, 1), (H, W))
    print(white_count - (path_length + 1))
    return

# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    s = [[c for c in next(tokens)] for _ in range(H)]  # type: "List[str]"
    solve(H, W, s)
    pass

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

total_white = 0
for i in s:
  total_white += i.count(".")

sh = 0
sw = 0
gh = H-1
gw = W-1

s[sh][sw] = 0
q = [[sh, sw]]
min_path = 0

while len(q) > 0:
  h, w = q.pop(0)
  if h == gh and w == gw:
    min_path = s[h][w]
    break
  for dh, dw in ([0, 1], [0, -1], [1, 0], [-1, 0]):
    if 0 <= h + dh < H and 0 <= w + dw < W:
      if s[h+dh][w+dw] == ".":
        s[h+dh][w+dw] = s[h][w] + 1
        q.append([h+dh, w+dw])

print(total_white - min_path -1)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
a=[]
for i in range(h):a.append(list(input()))
white=[flatten for inner in a for flatten in inner].count(".")
turn=1
a[-1][-1]=1
while turn in [flatten for inner in a for flatten in inner]:
    for i in range(h):
        for j in range(w):
            if a[i][j]==turn:
                if i>0 and a[i-1][j]==".":a[i-1][j]=turn+1
                if i<h-2 and a[i+1][j]==".":a[i+1][j]=turn+1
                if j>0 and a[i][j-1]==".":a[i][j-1]=turn+1
                if j<w-2 and a[i][j+1]==".":a[i][j+1]=turn+1
    turn+=1
    if a[0][0]!=".":break
print(-1 if a[0][0]=="." else white-a[0][0])

Submission status: Wrong Answer

Solution code:

import sys
from queue import Queue  # put/get


def parse(file):
    height, width = map(int, file.readline().split())
    maze = []
    for y in range(height):
        row = file.readline().strip()
        maze.append(row)

    return height, width, maze


def main(height, width, maze):
    traversed = [(0, 0)]
    queue = Queue()  # get/put

    queue.put((0, 0, 0))

    nwhite = 0
    for r in maze:
        nwhite += r.count('.')

    while not queue.empty():
        (y, x, count) = queue.get()

        if (y, x) == (height - 1, width - 1):
            return nwhite - count - 1
        for ny, nx in ((y - 1, x), (y + 1, x), (y, x - 1), (y, x + 1)):
            if ny >= height or nx >= width or ny < 0 or nx < 0:
                continue
            if (ny, nx) in traversed:
                continue
            if maze[ny][nx] == '.':
                queue.put((ny, nx, count + 1))
                traversed.append((ny, nx))


if __name__ == '__main__':
    print(main(*parse(sys.stdin)))

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
grid = [[c == "." for c in input()] for i in range(h)]
print(len(grid), len(grid[0]))
q = deque()
q.append((0,0,1))
visited = set()
min_dist = 0
while q:
    y, x, d = q.popleft()
    # 訪問済み、黒マスならスキップ
    if (y,x) in visited or not grid[y][x]:
        continue
    visited.add((y,x))
    # 終了条件
    if y == h-1 and x == w-1:
        min_dist = d
        break

    for dy, dx in [[-1,0],[1,0],[0,1],[0,-1]]:
        yn = y + dy
        xn = x + dx
        if 0<=yn<h and 0<=xn<w:
            q.append((yn, xn, d+1))
if min_dist:
    white = sum(sum(i) for i in grid)
    print(white - min_dist)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
grid = [[c == "." for c in input()] for i in range(h)]
white = sum(sum(i) for i in grid)

q = deque()
q.append((0,0))
grid[0][0] = 1
while q:
    y,x = q.pop()
    for dy, dx in [[-1,0],[1,0],[0,1],[0,-1]]:
        yn = y + dy
        xn = x + dx
        if 0<=yn<h and 0<=xn<w and grid[yn][xn] == True:
            grid[yn][xn] = grid[y][x] + 1
            q.appendleft((yn,xn))

if isinstance(grid[-1][-1], int):
    print(white - grid[-1][-1])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
grid = [[c == "." for c in input()] for i in range(h)]
white = sum(sum(i) for i in grid)

q = deque()
q.append((0,0))
grid[0][0] = 1
while q:
    y,x = q.pop()
    for dy, dx in [[-1,0],[1,0],[0,1],[0,-1]]:
        yn = y + dy
        xn = x + dx
        if 0<=yn<h and 0<=xn<w and grid[yn][xn] is True:
            grid[yn][xn] = grid[y][x] + 1
            q.appendleft((yn,xn))

if isinstance(grid[-1][-1], int):
    print(white - grid[-1][-1])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
grid = [[c == "." for c in input()] for i in range(h)]
white = sum(sum(i) for i in grid)

q = deque()
q.append((0,0))
grid[0][0] = 1
while q:
    y,x = q.pop()
    for dy, dx in [[-1,0],[1,0],[0,1],[0,-1]]:
        yn = y + dy
        xn = x + dx
        if 0<=yn<h and 0<=xn<w and grid[yn][xn] is True:
            grid[yn][xn] = grid[y][x] + 1
            q.append((yn,xn))

if isinstance(grid[-1][-1], int):
    print(white - grid[-1][-1])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
grid = [[c == "." for c in input()] for i in range(h)]
q = deque()
q.append((0,0,1))
visited = set()
min_dist = 0
while q:
    y, x, d = q.pop()
    if (y,x) in visited or not grid[y][x]:
        continue
    visited.add((y,x))
    if y == h-1 and x == w-1:
        min_dist = d
        break

    for dy, dx in [[-1,0],[1,0],[0,1],[0,-1]]:
        yn = y + dy
        xn = x + dx
        if 0<=yn<h and 0<=xn<w:
            q.append((yn, xn, d+1))
if min_dist:
    white = sum(sum(i) for i in grid)
    print(white - min_dist)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
grid = [[False]*w for i in range(h)]
white_cnt = 0
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == ".":
            grid[i][j] = True
            white_cnt += 1
grid[0][0] = grid[-1][-1] = True

q = deque()
q.append((0,0))
grid[0][0] = 1
while q:
    y, x = q.pop()
    for dy, dx in [[-1,0],[1,0],[0,1],[0,-1]]:
            yn = y + dy
            xn = x + dx
            if 0<=yn<h and 0<=xn<w and (grid[yn][xn] is True):
                grid[yn][xn] = grid[y][x] + 1
                q.append((yn, xn))
if grid[-1][-1] is True:
    print(-1)
else:
    print(white_cnt - grid[-1][-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
grid = [[False]*w for i in range(h)]
white_cnt = 0
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == ".":
            grid[i][j] = True
            white_cnt += 1
if not(grid[0][0] and grid[-1][-1]):
    print(-1)
    exit()

q = deque()
q.append((0,0))
grid[0][0] = 1
while q:
    y, x = q.pop()
    for dy, dx in [[-1,0],[1,0],[0,1],[0,-1]]:
            yn = y + dy
            xn = x + dx
            if 0<=yn<h and 0<=xn<w and (grid[yn][xn] is True):
                grid[yn][xn] = grid[y][x] + 1
                q.append((yn, xn))
if grid[-1][-1] is True:
    print(-1)
else:
    print(white_cnt - grid[-1][-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
cnt = [[-1] * w for _ in range(h)]

def bfs():
    queue = deque([[0, 0]])
    cnt[0][0] = 0
    while queue:
        i, j = queue.popleft()
        if [i, j] == [h - 1, w - 1]:
            return cnt[i][j]
        for di, dj in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            if (0 <= i + di < h and 0 <= j + dj < w and s[i + di][j + dj] == "." and cnt[i + di][j + dj] == -1):
                cnt[i + di][j + dj] = cnt[i][j] + 1
                queue.append([i + di, j + dj])

ans = -1
if bfs() == h + w - 2:
    ans = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                ans += 1
    ans = ans - (h + w - 1)
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

h, w = [int(x) for x in input().split()]
M = [input() for _ in range(h)]

p = [[None] * w for _ in range(h)]
q = collections.deque()

p[0][0] = 0
q.append((0, 0))

while len(q) > 0:
    x, y = q.popleft()
    for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        if x + dx == w - 1 and y + dy == h - 1:
            q.clear()
            break
        if 0 <= x + dx < w and 0 <= y + dy < h:
            if M[y + dy][x + dx] == '.':
                if p[y + dy][x + dx] is None:
                    p[y + dy][x + dx] = p[y][x] + 1
                    q.append((x + dx, y + dy))

print(sum(row.count('.') for row in M) - p[y][x] - 2)

Submission status: Wrong Answer

Solution code:
H, W = map(int, raw_input().split())
dungeon = []
memo = []
whitecount = 0
for i in range(0, H):
	dlst = []
	nlst = []
	s = raw_input()
	for j in range(0, W):
		if s[j] == '.': whitecount += 1
		dlst.append(s[j]=='.')
		nlst.append(H*W+1)
	dungeon.append(dlst)
	memo.append(nlst)
max = -1
queue = [[0, 0, 1]]
while queue != []:
	now = queue.pop(0)
	if now[2] < memo[now[0]][now[1]]:
		memo[now[0]][now[1]] = now[2]
		for i in range(0, 2):
			nexth = now[0] - 1 + 2*i
			nextw = now[1] - 1 + 2*i
			if 0 <= nexth and nexth < H:
				queue.append([nexth, now[1], now[2]+1])
			if 0 <= nextw and nextw < W:
				queue.append([now[0], nextw, now[2]+1])
if max < whitecount - memo[H-1][W-1]:
	max = whitecount-memo[H-1][W-1]
print max

Submission status: Wrong Answer

Solution code:
import queue

h,w = map(int, input().split())
s = [input() for i in range(h)]

white = 0

for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            white += 1

q = queue.Queue()

move = [[0,1],[0,-1],[1,0],[-1,0]]

q.put([0,0])

inf = float('inf')
d = [[inf for i in range(w)] for j in range(h)]
d[0][0] = 0

while not q.empty():
    p = q.get()
    for m in move:
        if 0<=p[0]+m[0]<h and 0<=p[1]+m[1]<w and d[p[0]+m[0]][p[1]+m[1]] == inf:
            d[p[0]+m[0]][p[1]+m[1]] = d[p[0]][p[1]]+1
            q.put([p[0]+m[0], p[1]+m[1]])

if d[h-1][w-1] ==inf:
    print(-1)
else:
    print(white-d[h-1][w-1]-1)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
s = [input()+'?' for _ in range(h)]
s.append('?'*(w+1))
dp = [[h*w]*(w+1) for _ in range(h+1)]
dp[0][0]=1
cnt = 0
for i in range(h):
    cnt += s[i].count('.')
    for j in range(w):
        if s[i][j+1]=='.':
            dp[i][j+1]=min(dp[i][j+1],dp[i][j]+1)
        if s[i+1][j]=='.':
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1)
        if i>0 and dp[i-1][j]=='.':
            dp[i-1][j]=min(dp[i-1][j],dp[i][j]+1)
        if j>0 and dp[i][j-1]=='.':
            dp[i][j-1]=min(dp[i][j-1],dp[i][j]+1)
for i in range(h):
    for j in range(w):
        if s[i][j+1]=='.':
            dp[i][j+1]=min(dp[i][j+1],dp[i][j]+1)
        if s[i+1][j]=='.':
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1)
        if i>0 and dp[i-1][j]=='.':
            dp[i-1][j]=min(dp[i-1][j],dp[i][j]+1)
        if j>0 and dp[i][j-1]=='.':
            dp[i][j-1]=min(dp[i][j-1],dp[i][j]+1)
if dp[h-1][w-1]==h*w:
    print(-1)
else:
    print(cnt-dp[h-1][w-1])

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
s = [input()+'?' for _ in range(h)]
s.append('?'*(w+1))
dp = [[h*w]*(w+1) for _ in range(h+1)]
dp[0][0]=1
cnt = 0
for i in range(h):
    cnt += s[i].count('.')
    for j in range(w):
        if s[i][j+1]=='.':
            dp[i][j+1]=min(dp[i][j+1],dp[i][j]+1)
        if s[i+1][j]=='.':
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1)
        if i>0 and dp[i-1][j]=='.':
            dp[i-1][j]=min(dp[i-1][j],dp[i][j]+1)
        if j>0 and dp[i][j-1]=='.':
            dp[i][j-1]=min(dp[i][j-1],dp[i][j]+1)
for i in range(h):
    for j in range(w):
        if s[i][j+1]=='.':
            dp[i][j+1]=min(dp[i][j+1],dp[i][j]+1)
        if s[i+1][j]=='.':
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1)
        if i>0 and dp[i-1][j]=='.':
            dp[i-1][j]=min(dp[i-1][j],dp[i][j]+1)
        if j>0 and dp[i][j-1]=='.':
            dp[i][j-1]=min(dp[i][j-1],dp[i][j]+1)
print(cnt-dp[h-1][w-1])

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
s = [input()+'?' for _ in range(h)]
s.append('?'*(w+1))
dp = [[h*w]*(w+1) for _ in range(h+1)]
dp[0][0]=1
cnt = 0
for i in range(h):
    cnt += s[i].count('#')
    for j in range(w):
        if s[i][j+1]=='.':
            dp[i][j+1]=min(dp[i][j+1],dp[i][j]+1)
        if s[i+1][j]=='.':
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1)
        if i>0 and dp[i-1][j]=='.':
            dp[i-1][j]=min(dp[i-1][j],dp[i][j]+1)
        if j>0 and dp[i][j-1]=='.':
            dp[i][j-1]=min(dp[i][j-1],dp[i][j]+1)
for i in range(h):
    for j in range(w):
        if s[i][j+1]=='.':
            dp[i][j+1]=min(dp[i][j+1],dp[i][j]+1)
        if s[i+1][j]=='.':
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1)
        if i>0 and dp[i-1][j]=='.':
            dp[i-1][j]=min(dp[i-1][j],dp[i][j]+1)
        if j>0 and dp[i][j-1]=='.':
            dp[i][j-1]=min(dp[i][j-1],dp[i][j]+1)
print(h*w-dp[h-1][w-1]-cnt)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
s = [input()+'?' for _ in range(h)]
s.append('?'*(w+1))
dp = [[h*w]*(w+1) for _ in range(h+1)]
dp[0][0]=1
cnt = 0
for i in range(h):
    cnt += s[i].count('#')
    for j in range(w):
        if s[i][j+1]=='.':
            dp[i][j+1]=min(dp[i][j+1],dp[i][j]+1)
        if s[i+1][j]=='.':
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1)
        if i>0 and dp[i-1][j]=='.':
            dp[i-1][j]=min(dp[i-1][j],dp[i][j]+1)
        if j>0 and dp[i][j-1]=='.':
            dp[i][j-1]=min(dp[i][j-1],dp[i][j]+1)
print(h*w-dp[h-1][w-1]-cnt)

Submission status: Wrong Answer

Solution code:
import queue
H,W=map(int, input().split())

inmap = [input() for _ in range(H)]

q = queue.Queue(10)
q.put((0,0,1))

cood = [(1,0),(-1,0),(0,1),(0,-1)]

res = 0

visited = set([(0,0)])

while not q.empty():
    x,y,cnt=q.get()
    # print(x,y)
    if x+1 == W and y+1 == H:
        res = cnt
        break
    for dx, dy in cood:
        if x+dx >= 0 and x+dx < W and y+dy >= 0 and y+dy < H:
            # print(visited)
            if inmap[y+dy][x+dx] != '#' and not (x+dx, y+dy) in visited:
                q.put((x+dx, y+dy, cnt+1))
                visited.add((x+dx, y+dy))

black = 0
for i in range(H):
    for j in range(W):
        if inmap[i][j] == '#':
            black += 1

# print((W-1, H-1) in visited)
print(H*W - black - res)

Submission status: Wrong Answer

Solution code:
H,W = list(map(int,input().split()))

M=[]

w_count=0

for i in range(H):
    s=input()
    m=[]
    for j in range(W):
        if s[j]=='.':
            m.append(0)
            w_count+=1
        else:
            m.append(1)
    M.append(m)

path = [[[] for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        if M[i][j]==0:
            if i!=H-1:
                if M[i+1][j]==0:
                    path[i][j].append([i+1,j])
                    path[i+1][j].append([i,j])
            if j!=W-1:
                if M[i][j+1]==0:
                    path[i][j].append([i,j+1])
                    path[i][j+1].append([i,j])

M_path = [[10**27 for j in range(W)] for i in range(H)]
M_checked = [[False for j in range(W)] for i in range(H)]
M_path[0][0]=0

from collections import deque

Q=deque([[0,0]])

while len(Q)>0:
    i,j=Q.pop()
    M_checked[i][j]=True
    mp = M_path[i][j]
    for p in path[i][j]:
        if not M_checked[p[0]][p[1]]:
            Q.append(p)
            if mp+1 < M_path[p[0]][p[1]]:
                M_path[p[0]][p[1]] = mp+1

if M_path[H-1][W-1]<10**27:
    print(w_count-(M_path[H-1][W-1]+1))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import Queue

H,W=map(int,raw_input().split())
s=[raw_input() for i in range(H)]
print(s)
q=Queue.Queue()
visited=[[False]*W for _ in range(H)]
dist=[[1145141919810]*W for _ in range(H)]
visited[0][0]=True
dist[0][0]=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
q.put((0,0))

while not q.empty():
    x,y=q.get()
    for i in range(4):  
        xx=x+dx[i]
        yy=y+dy[i]
        if (not 0<=xx<H) or (not 0<=yy<W): continue
        if s[xx][yy] == "#" :continue
        if visited[xx][yy]:continue
        visited[xx][yy]=True
        dist[xx][yy]=dist[x][y]+1
        q.put((xx,yy))
use=[[False]*W for _ in range(H)]
use[H-1][W-1]=True
use[0][0]=True
(x,y)=(H-1, W-1)
while (x,y) != (0,0):
    use[x][y]=True
    mpos=(-1,-1)
    mval=1145141919
    for i in range(4):
        xx=x+dx[i]
        yy=y+dy[i]
        if (not 0<=xx<H) or (not 0<=yy<W): continue     
        if dist[xx][yy] < mval:
            mpos=(xx,yy)
            mval=dist[xx][yy]
    x,y=mpos
cnt=0
for x in range(H):
    for y in range(W):
        if s[x][y] == "." and not use[x][y]: cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

from queue import Queue

h,w = map(int,input().split())
black, white = 0,0
s = [[0] * w for _ in range(h)]
for i in range(h):
    s[i] = list(input())
    for j in range(w):
        if s[i][j] == ".":
            white += 1
        else:
            black += 1

def bfs():
    global ans,checked
    while not que.empty():
        xy = que.get()
        if xy[0] == w - 1 and xy[1] == h - 1:
            ans = checked[xy[1]][xy[0]]
            return
        for i in range(-1,2):
            for j in range(-1,2):
                if i == j or i == -j:
                    continue
                if 0 <= xy[0] + i < w and 0 <= xy[1] + j < h:
                    if checked[xy[1] + j][xy[0] + i] == -1 and s[xy[1] + j][xy[0] + i] == ".":
                        checked[xy[1] + j][xy[0] + i] = checked[xy[1]][xy[0]] + 1
                        que.put([xy[0] + i,xy[1] + j])

que = Queue()
ans = 0
checked = [[-1] * w for _ in range(h)]
checked[0][0] = 0
que.put([0,0])

bfs()
print(white - ans - 1)

Submission status: Wrong Answer

Solution code:
h, w = [int(i) for i in input().split(" ")]
s = ["" for i in range(0, h)]

for i in range(0, h):
    s[i] = input()

d = [[[-1, -1] for j in range(0, w)] for i in range(0, h)]

def trav(i, j, b):
    global s
    d[i][j] = b
    if i == h - 1 and j == w - 1:
        return True
    if j < w - 1 and s[i][j + 1] == "." and trav(i, j + 1, [i, j]):
        return True
    elif i < h - 1 and s[i + 1][j] == "." and trav(i + 1, j, [i, j]):
        return True
    else:
        return False

c = 0
for i in range(0, h):
    for j in range(0, w):
        if s[i][j] == ".":
            c += 1

if trav(0, 0, [-1, -1]):
    k = d[h - 1][w - 1]
    while k != [0, 0]:
        k = d[k[0]][k[1]]
        c -= 1
    print(c - 2)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = [int(item) for item in input().split()]
s = [input() for _ in range(h)]
dist = [[-1] * w for _ in range(h)]

black = 0
for line in s:
  black += line.count("#")

que = deque()
que.append([0,0])
dist[0][0] = 1
while que:
  x, y = que.popleft()
  for i, j in [(1,0), (-1,0), (0,1), (0,-1)]:
    nx = x + i
    ny = y + j
    if nx < 0 or nx >= h or ny < 0 or ny >= w:
      continue
    if s[nx][ny] == "#":
      continue
    if dist[nx][ny] == -1:
      dist[nx][ny] = dist[x][y] + 1
      que.append([nx, ny])

print(h*w - dist[h-1][w-1] - black)

Submission status: Wrong Answer

Solution code:
def serch(x,y,p):
    if x<0 or W<=y or y<0 or H<=x or meiro[x][y] =="#":
        return
    if memo[x][y]:
        p = [x,y]
        return
    memo[x][y] = 1
    kyo[x][y] = kyo[p[0]][p[1]] + 1
    p = [x,y]
    serch(x+1,y,p)
    serch(x-1,y,p)
    serch(x,y+1,p)
    serch(x,y-1,p)
H,W = list(map(int,input().split()))
sx,sy = 0,0
gx,gy = H-1,W-1
meiro = [list(input()) for l in range(H)]
counter = 0
for a in range(H):
    for b in range(W):
        n = 1 if meiro[a][b] =="." else 0
        counter += n
dx = [1,0,-1,0]
dy = [0,1,0,-1]
stk = [(sx,sy)]

memo =[[0 for i in range(W)] for l in range(H)]
memo[sx][sy]=1
dis =[[0 for i in range(W)] for l in range(H)]
while stk:
    x,y = stk.pop(0)
    for i in range(4):
        xx,yy = x+dx[i],y+dy[i]
        if xx<0 or W<=yy or yy<0 or H<=xx or meiro[xx][yy] =="#" or memo[xx][yy]==True:
            continue
        dis[xx][yy] = dis[x][y]+1
        stk.append((xx,yy))
        memo[xx][yy] = 1
print(counter-dis[gx][gy]-1)

Submission status: Wrong Answer

Solution code:
from queue import Queue

H, W =  list(map(int, input().split()))
s = [input() for _ in range(H)]
 
y = "."
n = "#"

D = [[0] * W for _ in range(H)]
num = 0
for i in range(H):
  for j in range(W):
    if s[i][j] == y:
      num += 1
    else:
      D[i][j] = -1

def setWall(D, x):
  H = len(D)
  W = len(D[0]) + 2
  D = [[x] * W] + [[x] + [i for i in j] + [x] for j in D] + [[x] * W] 
  return D

D = setWall(D, -1)

D[1][1] = 1
Q = Queue()
Q.put([1, 1])
while Q.empty() != True:
  x, y = Q.get()
  t = D[x][y]
  for i in (-1, 1):
    for j in (0, 1):
      a = j * i
      b = (1 - j) * i
      if D[x + a][y + b] > t + 1 or D[x + a][y + b] == 0:
        D[x + a][y + b] = t + 1
        Q.put([x + a, y + b])

print(num - D[H][W])

Submission status: Wrong Answer

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


H,W = map(int, input().split())
num_w = -1
srch = []
for i in range(H):
  h = list(str(sys.stdin.readline().rstrip()))
  for j in range(W):
    if h[j] == ".":
      srch.append([i+1,j+1])
      num_w += 1

Cn = [[sys.maxsize for j in range(W+2)] for i in range(H+2)]
Cn[1][1] = 0
while(Cn[H][W] == sys.maxsize):
  for i,j in srch[1:]:
    Cn[i][j] = min(Cn[i-1][j],Cn[i][j-1],Cn[i+1][j],Cn[i][j+1])+1

print(num_w - Cn[H][W])

Submission status: Wrong Answer

Solution code:
H, W=map(int, input().split())
graph=[]
road=0
for i in range(H):
    s=list(input())
    road=road+s.count(".")
    graph.append(s)

not_visited=[]
not_visited=[[True for i in range(W)] for j in range(H)]
need_visited=[]
need_visited=[[0 for i in range(W)] for j in range(H)]
need_visited[H-1][W-1]=True
queue=[]

dx=[1, -1, 0, 0]
dy=[0, 0, 1, -1]

start_point=[0, 0]
queue.append(start_point)
while len(queue)!=0:
    now_point=queue.pop(0)
    for i in range(4):
        search_point=[now_point[0]+dx[i], now_point[1]+dy[i]]
        if 0<=search_point[0]<H and 0<=search_point[1]<W:
            if graph[search_point[0]][search_point[1]]!="#" and not_visited[search_point[0]][search_point[1]]:
                not_visited[search_point[0]][search_point[1]]=False
                queue.append(search_point)
                need_visited[search_point[0]][search_point[1]]=need_visited[now_point[0]][now_point[1]]+1
if need_visited[H-1][W-1]:
    print(-1)
else:
    print(road-need_visited[H-1][W-1]-1)

Submission status: Wrong Answer

Solution code:
H, W=map(int, input().split())
graph=[]
road=0
for i in range(H):
    s=list(input())
    road=road+s.count(".")
    graph.append(s)

not_visited=[]
not_visited=[[True for i in range(W)] for j in range(H)]
need_visited=[]
need_visited=[[0 for i in range(W)] for j in range(H)]
queue=[]

dx=[1, -1, 0, 0]
dy=[0, 0, 1, -1]

start_point=[0, 0]
queue.append(start_point)
while len(queue)!=0:
    now_point=queue.pop(0)
    for i in range(4):
        search_point=[now_point[0]+dx[i], now_point[1]+dy[i]]
        if 0<=search_point[0]<H and 0<=search_point[1]<W:
            if graph[search_point[0]][search_point[1]]!="#" and not_visited[search_point[0]][search_point[1]]:
                not_visited[search_point[0]][search_point[1]]=False
                queue.append(search_point)
                need_visited[search_point[0]][search_point[1]]=need_visited[now_point[0]][now_point[1]]+1
print(road-need_visited[H-1][W-1]-1)

Submission status: Wrong Answer

Solution code:
import collections

H,W=map(int,input().split())
s=[]
for i in range(H):
    s.append(input())
ans=0
for i in range(H):
    ans+=s[i].count('.')

inf=1<<60
c=[[inf for j in range(W)] for i in range(H)]
c[0][0]=1

q=collections.deque()
q.append((0,0))
try:
    while True:
        y,x=q.popleft()
        if x>1 and s[y][x-1]=='.' and c[y][x-1]>c[y][x]+1:
            c[y][x-1]=c[y][x]+1
            q.append((y,x-1))
        if x<W-1 and s[y][x+1]=='.' and c[y][x+1]>c[y][x]+1:
            c[y][x+1]=c[y][x]+1
            q.append((y,x+1))
        if y>1 and s[y-1][x]=='.' and c[y-1][x]>c[y][x]+1:
            c[y-1][x]=c[y][x]+1
            q.append((y-1,x))
        if y<H-1 and s[y+1][x]=='.' and c[y+1][x]>c[y][x]+1:
            c[y+1][x]=c[y][x]+1
            q.append((y+1,x))
except IndexError:
    pass
if c[H-1][W-1]==inf:
    print(-1)
else:
    print(ans-c[H-1][W-1])

Submission status: Wrong Answer

Solution code:
import collections

H,W=map(int,input().split())
s=[]
for i in range(H):
    s.append(input())
ans=0
for i in range(H):
    ans+=s[i].count('.')

inf=1<<60
c=[[inf for j in range(W)] for i in range(H)]
c[0][0]=1

q=collections.deque()
q.append((0,0))
try:
    while True:
        y,x=q.popleft()
        if x>1 and s[y][x-1]=='.' and c[y][x-1]>c[y][x]+1:
            c[y][x-1]=c[y][x]+1
            q.append((y,x-1))
        if x<W-1 and s[y][x+1]=='.' and c[y][x+1]>c[y][x]+1:
            c[y][x+1]=c[y][x]+1
            q.append((y,x+1))
        if y>1 and s[y-1][x]=='.' and c[y-1][x]>c[y][x]+1:
            c[y-1][x]=c[y][x]+1
            q.append((y-1,x))
        if y<H-1 and s[y+1][x]=='.' and c[y+1][x]>c[y][x]+1:
            c[y+1][x]=c[y][x]+1
            q.append((y+1,x))
except IndexError:
    pass
print(ans-c[H-1][W-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(board, visited, gh, gw):
    turn = 0
    queue = deque([[0, 0, turn]])
    while queue:
        h, w, turn = queue.popleft()
        if h == gh-1 and w == gw-1:
            return turn
        for i, j in ([1,0],[-1,0],[0,1],[0,-1]):
            new_h, new_w = h+i, w+j
            if new_h >= gh or new_h < 0 or new_w >= gw or new_w < 0:
                continue
            elif board[new_h][new_w] != "#" and visited[new_h][new_w] == "x":
                visited[new_h][new_w] = "o"
                queue.append([new_h, new_w, turn+1])
    return turn

def main():
    H, W = map(int,input().split())
    board = []
    for _ in range(H):
        board.append(list(input()))
    black = 0
    for i in range(H):
        for j in range(W):
            if board[i][j] == "#":
                black += 1
    visited = [["x"]*W for _ in range(H)]
    path_area = bfs(board, visited, H, W) + 1
    print(H*W-path_area-black)
                
    
    
if __name__ == "__main__":
    main()