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:
from collections import deque
h, w = map(int, input().split())
maze = []
total_white_square = 0
for i in range(h):
    row = list(input())
    total_white_square += row.count('.')
    maze.append(row)
visited = [[False for i in range(w)] for j in range(h)]
queue = deque()
start = (0, 0)
end = (h - 1, w - 1)
queue.append((start, 1))
visited[0][0] = True
num_white_row = 0
while len(queue) > 0:
    curr, time = queue.popleft()
    if curr == end:
        num_white_row = time
        break
    x, y = curr
    if x - 1 >= 0 and not visited[x - 1][y] and maze[x - 1][y] == '.':
        visited[x - 1][y] = True
        queue.append(((x - 1, y), time + 1))
    if x + 1 <= h - 1 and not visited[x + 1][y] and maze[x + 1][y] == '.':
        visited[x + 1][y] = True
        queue.append(((x + 1, y), time + 1))
    if y - 1 >= 0 and not visited[x][y - 1] and maze[x][y - 1] == '.':
        visited[x][y - 1] = True
        queue.append(((x, y - 1), time + 1))
    if y + 1 <= w - 1 and not visited[x][y + 1] and maze[x][y + 1] == '.':
        visited[x][y + 1] = True
        queue.append(((x, y + 1), time + 1))
print(total_white_square - num_white_row)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(lambda x: int(x), input().split())
s=[[] for _ in range(h)]
black=0
for i in range(h):
    s[i]=input()
    black+=s[i].count('#')

dist=[[-1 for _ in range(w)] for _ in range(h)]
que = deque([(0, 0)])
dist[0][0]=0
while que:
    y, x=que.popleft()
    for y1, x1 in [(y-1, x), (y+1, x), (y, x-1), (y, x+1)]:
        if y1<0 or y1>h-1 or x1<0 or x1>w-1:
            continue
        if s[y1][x1]=='#':
            continue
        if dist[y1][x1]!=-1:
            continue
        dist[y1][x1]=dist[y][x]+1
        que.append((y1,x1))

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

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, input().rstrip('\n').split()))
    s = []
    b_cnt = 0
    for i in range(h):
        st = list(str(input().rstrip('\n')))
        s.append(st)
        b_cnt += st.count("#")

    ql = [[0, 0, 0]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(int)
    fq[0, 0] = 1
    m_cost = 10 ** 10
    while True:
        if len(ql) != 0:
            cost, x, y = ql.popleft()
            if x == h - 1 and y == w - 1:
                m_cost = min(m_cost, cost)
            for x, y in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
                if 0 <= x < h and 0 <= y < w:
                    if (x, y) not in fq and s[x][y] == ".":
                        ql.append([cost+1, x, y])
                        fq[x, y] += 1
        else:
            break
    print(h * w - b_cnt - m_cost - 1)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
r,c=map(int,input().split())
meiro=[list(input()) for i in range(r)]
#迷路の白マスを数える作業
white=0
for i in range(r):
    for j in range(c):
        if meiro[i][j]==".":
            white+=1
#迷路の外を＃で囲む
for i in range(r):
    meiro[i].insert(c,"#")
    meiro[i].insert(0,"#")
meiro.insert(0,["#"]*(c+2))
meiro.append(["#"]*(c+2))
#print(meiro)囲えた
idou=[[0,1],[0,-1],[1,0],[-1,0]]
tesuu=[[-1]*(c+2) for i in range(r+2)]
from collections import deque
tesuu[1][1]=1
#print(tesuu)
quest=deque([[1,1]])#最初に見る場所
while len(quest)!=0:
    see=quest.popleft()
    for i in idou:
        if meiro[see[0]+i[0]][see[1]+i[1]]=="#":
            continue
        if tesuu[see[0]+i[0]][see[1]+i[1]]!=-1:
            continue
        quest.append([see[0]+i[0],see[1]+i[1]])
        tesuu[see[0]+i[0]][see[1]+i[1]]=tesuu[see[0]][see[1]]+1
#print(meiro)
#print(tesuu[r][c])
print(white-tesuu[r][c])

Submission status: Wrong Answer

Solution code:
r,c=map(int,input().split())
meiro=[list(input()) for i in range(r)]
#迷路の白マスを数える作業
white=0
for i in range(r):
    for j in range(c):
        if meiro[i][j]==".":
            white+=1
#迷路の外を＃で囲む
for i in range(r):
    meiro[i].insert(c,"#")
    meiro[i].insert(0,"#")
meiro.insert(0,["#"]*(c+2))
meiro.append(["#"]*(c+2))
#print(meiro)囲えた
idou=[[0,1],[0,-1],[1,0],[-1,0]]
tesuu=[[-1]*(c+2) for i in range(r+2)]
from collections import deque
tesuu[1][1]=1
print(tesuu)
quest=deque([[1,1]])#最初に見る場所
while len(quest)!=0:
    see=quest.popleft()
    for i in idou:
        if meiro[see[0]+i[0]][see[1]+i[1]]=="#":
            continue
        if tesuu[see[0]+i[0]][see[1]+i[1]]!=-1:
            continue
        quest.append([see[0]+i[0],see[1]+i[1]])
        tesuu[see[0]+i[0]][see[1]+i[1]]=tesuu[see[0]][see[1]]+1
#print(meiro)
#print(tesuu[r][c])
print(white-tesuu[r][c])

Submission status: Wrong Answer

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

Q = [(0, 0, 0)]
ans = float("inf")
flag = False
while Q:
    i, j, n = Q.pop()
    if i == H-1 and j == W-1:
        flag = True
        ans = min(ans, n)
    if S[i][j] == ".":
        S[i][j] = "#"
        for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            if 0 <= i + dx < H and 0 <= j + dy < W:
                Q.append((i+dx, j+dy, n+1))
if flag:
    print((w-2)-(ans-1))
else:
    print(-1)

Submission status: Wrong Answer

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

Q = [(0, 0, 0)]
ans = float("inf")
while Q:
    i, j, n = Q.pop()
    if i == H-1 and j == W-1:
        ans = min(ans, n)
    if S[i][j] == ".":
        S[i][j] = "#"
        for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            if 0 <= i + dx < H and 0 <= j + dy < W:
                Q.append((i+dx, j+dy, n+1))

print((w-2)-(ans-1))

Submission status: Wrong Answer

Solution code:
def in_map(x,y):
	return 0 <= x <= w-1 and 0 <= y <= h-1

def bfs(maze,y,x):
	if maze[y][x] == goal:
		return [(y,x)]
	maze[y][x] = wall
	for (next_y,next_x) in [(y+1, x), (y, x+1), (y, x-1), (y-1, x)]:
		if not in_map(next_x,next_y):
			continue
		if maze[next_y][next_x] == wall :
			continue
		route = bfs(maze,next_y,next_x)
		if route:
			return [(y,x)] + route

h,w = map(int,input().split())
maze = []
start = (0,0)
wall = 1
goal = 2
block = 0
for i in range(h):
	row = input()
	row_int = []
	for i in list(row):
		if i == "#":
			row_int.append(1)
			block += 1
		elif i == ".":
			row_int.append(0)
	maze.append(row_int)

if maze[h-1][w-1] == wall:
	print(-1)
else :
	maze[h-1][w-1] = goal
	path = bfs(maze,0,0)
	if path != None :
		print(h*w - len(path) - block)
	else :
		print(-1)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
maze = []
start = (0,0)
wall = 1
goal = 2
block = 0
for i in range(h):
	row = input()
	row_int = []
	for i in list(row):
		if i == "#":
			row_int.append(1)
			block += 1
		elif i == ".":
			row_int.append(0)
	maze.append(row_int)

maze[h-1][w-1] = 2

def in_map(x,y):
	return 0 <= x <= w-1 and 0 <= y <= h-1

def bfs(maze,y,x):
	if maze[y][x] == goal:
		return [(y,x)]
	maze[y][x] = wall
	for (next_y,next_x) in [(y+1, x), (y, x+1), (y, x-1), (y-1, x)]:
		if not in_map(next_x,next_y):
			continue
		if maze[next_y][next_x] == wall :
			continue
		route = bfs(maze,next_y,next_x)
		if route:
			return [(y,x)] + route

path = bfs(maze,0,0)
if path != None :
	print(h*w - h+w-1 - block)
else :
	print(-1)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
maze = []
start = (0,0)
wall = 1
goal = 2
block = 0
for i in range(h):
	row = input()
	row_int = []
	for i in list(row):
		if i == "#":
			row_int.append(1)
			block += 1
		elif i == ".":
			row_int.append(0)
	maze.append(row_int)

maze[h-1][w-1] = 2

def in_map(x,y):
	return 0 <= x <= w-1 and 0 <= y <= h-1

def bfs(maze,y,x):
	if maze[y][x] == goal:
		return [(y,x)]
	maze[y][x] = wall
	for (next_y,next_x) in [(y+1, x), (y, x+1), (y, x-1), (y-1, x)]:
		if not in_map(next_x,next_y):
			continue
		if maze[next_y][next_x] == wall :
			continue
		route = bfs(maze,next_y,next_x)
		if route:
			return [(y,x)] + route

path = bfs(maze,0,0)
if path != None :
	print(h*w - len(path) - block)
else :
	print(-1)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
maze = []
start = (0,0)
wall = 1
goal = 2
block = 0
for i in range(h):
	row = input()
	row_int = []
	for i in list(row):
		if i == "#":
			row_int.append(1)
			block += 1
		elif i == ".":
			row_int.append(0)
	maze.append(row_int)

maze[h-1][w-1] = 2

def in_map(x,y):
	return 0 <= x <= w-1 and 0 <= y <= h-1

def bfs(maze,y,x):
	if maze[y][x] == goal:
		return [(y,x)]
	maze[y][x] = wall
	for (next_y,next_x) in [(y+1, x), (y, x+1), (y, x-1), (y-1, x)]:
		if not in_map(next_x,next_y):
			continue
		if maze[next_y][next_x] == wall :
			continue
		route = bfs(maze,next_y,next_x)
		if route:
			return [(y,x)] + route

print(h*w - h+w -1 - block)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import deque

def main():
    H,W = map(int,input().split())
    S = [list(input()) for _ in range(H)]
    white_count = 0

    for s in S:
        for ss in s:
            if ss == ".":
                white_count+=1

    vector = [[1,0],[-1,0],[0,-1],[0,1]]
    min_distance = [[float('inf')]*W for _ in range(H)]
    queue = deque([[0,0]])
    min_distance[0][0] = 0

    while queue:
        q = queue.popleft()
        for v in vector:
            nqy = q[0]+v[0]
            nqx = q[1]+v[1]

            if nqx>=0 and nqy>=0 and nqx<=W-1 and nqy<=H-1 and min_distance[nqy][nqx]==float('inf') and S[nqy][nqx]!="#":
                queue.append([nqy,nqx])
                min_distance[nqy][nqx]=min_distance[q[0]][q[1]]+1

    print(white_count - min_distance[H-1][W-1]-1)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W=map(int,input().split())

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

sx,sy=0,0

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

def bfs(sx,sy,l):
  que=deque()
  que.append([sx,sy])
  count=[[-1]*W for _ in range(H)]
  count[sx][sy]=0
  dx=[1,-1,0,0]
  dy=[0,0,1,-1]
  while que:
    x,y=que.popleft()
    if x==H-1 and y==W-1:
      return count[x][y]
    for j in range(4):
      a,b=x+dx[j],y+dy[j]
      if a<0 or a>=H or b<0 or b>=W or count[a][b]!=-1 or l[a][b]=='#':
        continue
      else:
        count[a][b]=count[x][y]+1
        que.append([a,b])
  return 0
print(H*W-(bfs(sx,sy,l)+black+1))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        H, W = map(int, input().split())
        field = defaultdict(lambda: '#')
        dot_cnt = 0
        for h in range(H):
            for w, c in enumerate(list(input().rstrip())):
                field[str(h + 1) + '-' + str(w + 1)] = c
                if c == '.':
                    dot_cnt += 1

        q = [(1, 1)]
        field['1-1'] = '#'
        moving_range = ((1, 0), (-1, 0), (0, 1), (0, -1))
        moves = 1
        while q:
            if (H, W) in q:
                break

            next_q = []
            for x, y in q:
                for m_x, m_y in moving_range:
                    n_x, n_y = x + m_x, y + m_y
                    if field[str(n_x) + '-' + str(n_y)] == '.':
                        next_q.append((n_x, n_y))
                        field[str(n_x) + '-' + str(n_y)] = '#'
            moves += 1
            q = next_q
            if len(q) == 0:
                print(-1)
                break

        print(dot_cnt - moves)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        H, W = map(int, input().split())
        field = defaultdict(lambda: '#')
        dot_cnt = 0
        for h in range(H):
            for w, c in enumerate(list(input().rstrip())):
                field[str(h + 1) + '-' + str(w + 1)] = c
                if c == '.':
                    dot_cnt += 1

        q = [(1, 1)]
        field['1-1'] = '#'
        moving_range = ((1, 0), (-1, 0), (0, 1), (0, -1))
        moves = 1
        while q:
            if (H, W) in q:
                break

            next_q = []
            for x, y in q:
                for m_x, m_y in moving_range:
                    n_x, n_y = x + m_x, y + m_y
                    if field[str(n_x) + '-' + str(n_y)] == '.':
                        next_q.append((n_x, n_y))
                        field[str(n_x) + '-' + str(n_y)] = '#'
            moves += 1
            q = next_q
            if not q:
                print(-1)
                break

        print(dot_cnt - moves)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Wrong Answer

Solution code:
import sys
import os
from collections import deque

INF = 10**5
H, W = map(int,input().split())
S = ["" for _ in range(H)]
cntSharp = 0
for i in range(H):
    S[i] = input()
    cntSharp += S[i].count("#")

dp = [[INF for _ in range(W)] for _ in range(H)]
dp[0][0] = 0
#移動用のベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]
P = deque([])
P.append((0,0))
while P:
    p = P.popleft()
    s,t = p[0], p[1]
    for i in range(4):
        nx,ny = s + dx[i], t + dy[i]
        if 0 <= nx and 0 <= ny and nx <= H-1 and ny <= W-1 and S[nx][ny] =="." and dp[nx][ny] == INF:
            dp[nx][ny] = dp[s][t] + 1
            P.append((nx,ny))
print(dp)
if dp[H-1][W-1] == INF:
    print(-1)
else:
    print(H*W - dp[H-1][W-1] - cntSharp - 1)

Submission status: Wrong Answer

Solution code:
import sys
import os
import heapq

INF = 10**5
H, W = map(int,input().split())
S = ["" for _ in range(H)]
cntSharp = 0
for i in range(H):
    S[i] = input()
    cntSharp += S[i].count("#")

dp = [[INF for _ in range(W)] for _ in range(H)]
dp[0][0] = 0
#移動用のベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]
P = [(0,0)]
heapq.heapify(P)
while P:
    p = heapq.heappop(P)
    s,t = p[0], p[1]
    for i in range(4):
        nx,ny = s + dx[i], t + dy[i]
        if 0 <= nx and 0 <= ny and nx <= H-1 and ny <= W-1 and S[nx][ny] =="." and dp[nx][ny] == INF:
            dp[nx][ny] = dp[s][t] + 1
            heapq.heappush(P,(nx,ny))
if dp[H-1][W-1] == INF:
    print(-1)
else:
    print(H*W - dp[H-1][W-1] - cntSharp - 1)

Submission status: Wrong Answer

Solution code:
import sys
import os
import heapq

INF = 10**5
H, W = map(int,input().split())
S = ["" for _ in range(H)]
cntSharp = 0
for i in range(H):
    S[i] = input()
    cntSharp += S[i].count("#")

dp = [[INF for _ in range(W)] for _ in range(H)]
dp[0][0] = 0
#移動用のベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]
P = [(0,0)]
heapq.heapify(P)
while len(P)>0:
    p = heapq.heappop(P)
    s = p[0]
    t = p[1]
    for i in range(4):
        nx = s + dx[i]
        ny = t + dy[i]
        if 0 <= nx and 0 <= ny and nx <= H-1 and ny <= W-1 and S[nx][ny] =="." and dp[nx][ny] == INF:
            dp[nx][ny] = dp[s][t]+1
            heapq.heappush(P,(nx,ny))
if dp[H-1][W-1] == INF:
    print(-1)
else:
    print(H*W-dp[H-1][W-1]-cntSharp-1)

Submission status: Wrong Answer

Solution code:
import sys
import os
import heapq
INF = 10**5
H, W = map(int,input().split())
S = ["" for _ in range(H)]
cntSharp = 0
for i in range(H):
    S[i] = input()
    cntSharp += S[i].count("#")

dp = [[INF for _ in range(W)] for _ in range(H)]
dp[0][0] = 0
#移動用のベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]
P = [(0,0)]
heapq.heapify(P)
while len(P)>0:
    p = heapq.heappop(P)
    s = p[0]
    t = p[1]
    if s == W-1 and t == H-1:
        break
    for i in range(4):
        nx = s + dx[i]
        ny = t + dy[i]
        if 0 <= nx and 0 <= ny and nx <= H-1 and ny <= W-1 and S[nx][ny] =="." and dp[nx][ny] == INF:
            dp[nx][ny] = dp[s][t]+1
            heapq.heappush(P,(nx,ny))
if dp[H-1][W-1] == INF:
    print(-1)
else:
    print(H*W-dp[H-1][W-1]-cntSharp-1)

Submission status: Wrong Answer

Solution code:
import sys
import os
import heapq
INF = 10**5
H, W = map(int,input().split())
S = ["" for _ in range(H)]
cntSharp = 0
for i in range(H):
    S[i] = input()
    cntSharp += S[i].count("#")

dp = [[INF for _ in range(W)] for _ in range(H)]
dp[0][0] = 0
#移動用のベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]
P = [(0,0)]
heapq.heapify(P)
while len(P)>0:
    p = heapq.heappop(P)
    s = p[0]
    t = p[1]
    if s == W-1 and t == H-1:
        break
    for i in range(4):
        nx = s + dx[i]
        ny = t + dy[i]
        if 0 <= nx and 0 <= ny and nx <= H-1 and ny <= W-1 and S[nx][ny] =="." and dp[nx][ny] == INF:
            dp[nx][ny] = dp[s][t]+1
            heapq.heappush(P,(nx,ny))
print(H*W-dp[H-1][W-1]-cntSharp-1)

Submission status: Wrong Answer

Solution code:
def main():
    H, W = (int(i) for i in input().split())
    c = [input() for j in range(H)]
    sh, sw = 0, 0
    gh, gw = H-1, W-1

    from collections import deque
    def bfs():
        que = deque()
        dist = [[-1]*W for i in range(H)]

        dist[sh][sw] = 0
        que.append((sh,sw))
        d = ((1,0),(0,1),(-1,0),(0,-1))
        while que:
            uy,ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W): continue
                if dist[next_y][next_x] != -1: continue
                if c[next_y][next_x] == '#': continue
                dist[next_y][next_x] = dist[uy][ux] + 1
                que.append((next_y, next_x))
                if next_y == gh and next_x == gw:
                    return dist[gh][gw]
        return -(10**7)
    
    white_cnt = -1
    for i in range(H):
        for j in range(W):
            if c[i][j] == '.': white_cnt += 1
    
    goal = bfs()
    print(white_cnt - goal if goal != -1 else -1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    H, W = (int(i) for i in input().split())
    c = [input() for j in range(H)]
    sh, sw = 0, 0
    gh, gw = H-1, W-1

    from collections import deque
    def bfs():
        que = deque()
        dist = [[-1]*W for i in range(H)]

        dist[sh][sw] = 0
        que.append((sh,sw))
        d = ((1,0),(0,1),(-1,0),(0,-1))
        while que:
            uy,ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W): continue
                if dist[next_y][next_x] != -1: continue
                if c[next_y][next_x] == '#': continue
                dist[next_y][next_x] = dist[uy][ux] + 1
                que.append((next_y, next_x))
                if next_y == gh and next_x == gw:
                    return dist[gh][gw]
        return -(10**7)
    
    white_cnt = -1
    for i in range(H):
        for j in range(W):
            if c[i][j] == '.': white_cnt += 1
    print(white_cnt - bfs())

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
M = [list(input()) for i in range(H)]

INF = 10 ** 5
d = [[INF for i in range(W)] for j in range(H)]
d[0][0] = 0
nexts = [(-1, 0), (1, 0), (0, -1), (0, 1)]
q = deque()
q.append((0, 0))
while len(q) > 0:
  x, y = q.popleft()
  for dx, dy in nexts:
    nx, ny = x+dx, y+dy
    if nx < 0 or nx >= W or ny < 0 or ny >= H:
      continue
    if M[ny][nx] == '#' or d[ny][nx] != INF:
      continue
    d[ny][nx] = d[y][x] + 1
    q.append((nx, ny))

if d[H-1][W-1] == INF:
  print(-1)
else:
  res = 0
  for y in range(H):
    for x in range(W):
      if M[y][x] == '#':
        continue
      res += 1
  print(res-(H+W-1))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

gx, gy = w-1, h-1

q = deque()
q.appendleft([0,0])
INF = 10**5

dist = [[INF]*w for _ in range(h)]
dist[0][0] = 0

while q:
  x,y = q.pop()
  
  for dx,dy in [[1,0],[0,1],[-1,0],[0,-1]]:
    nx = x+dx
    ny = y+dy
    
    if 0<=nx<w and 0<=ny<h:
      if dist[ny][nx]==INF and maze[ny][nx] != '#':
        dist[ny][nx] = dist[y][x]+1
        q.appendleft([nx,ny])      

black_num = sum([maze[i].count('#') for i in range(h)])
print( h*w - dist[gy][gx] - black_num -1 )

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
maze = [input() for _ in range(H)]
p_flg = [[0]*W for _ in range(H)]
dyx = [(-1,0),(1,0),(0,-1),(0,1)]

def bfn(y,x,cnt):
    stack = [(y,x,cnt)]
    p_flg[y][x] = cnt
    while stack:
        sy, sx, cnt= stack.pop(0)
        cnt += 1
        for dy, dx in dyx:
            ny, nx = sy+dy, sx+dx
            if ny == H-1 and nx == W-1:
                return cnt
            elif 0<=ny<H and 0<=nx<W:
                if maze[ny][nx] !="#" and not p_flg[ny][nx]:
                    p_flg[ny][nx] = cnt
                    stack.append((ny,nx,cnt))
    return -1

def main():
    n_obs = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == "#":
                n_obs += 1
    n_path = bfn(0,0,1) -1
    ans = H*W - n_obs - n_path -1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def mod_idx(num: str):
    return int(num) - 1


h, w = map(mod_idx, input().split())
S = [list(input()) for _ in range(h + 1)]

# スタートとゴールを明示しておく。
sy, sx = 0, 0
gy, gx = h, w

inf = -1
shortest = [[inf] * (w + 1) for _ in range(h + 1)]
# ４方向へのステップ
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
que = deque()


def bfs():
    que.append([sy, sx])
    shortest[sy][sx] = 0

    while len(que):
        p = que.popleft()
        if p[0] == gy and p[1] == gx:
            break

        # 移動しましょう
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]

            # 未踏？
            if 0 <= nx <= w and 0 <= ny <= h and S[ny][nx] != "#" and shortest[ny][nx] == inf:
                que.append([ny, nx])
                shortest[ny][nx] = shortest[p[0]][p[1]] + 1
    return shortest[gy][gx]


# 全体の白いマスを数える
min_steps = bfs()
white_cnt = sum(line.count(".") for line in S)

print(white_cnt - min_steps - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque


def mod_idx(num: str):
    return int(num) - 1


h, w = map(mod_idx, input().split())
S = [list(input()) for _ in range(h+1)]

# スタートとゴールを明示しておく。
sy, sx = 0, 0
gy, gx = h, w

inf = 1000000000
shortest = [[inf] * (w+1) for _ in range(h+1)]
# ４方向へのステップ
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
que = deque()


def dfs():
    que.append([sy, sx])
    shortest[sy][sx] = 0

    while len(que):
        p = que.popleft()
        if p[0] == gy and p[1] == gx:
            break

        # 移動しましょう
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]

            # 未踏？
            if 0 <= nx <= w and 0 <= ny <= h and S[ny][nx] != "#" and shortest[ny][nx] == inf:
                que.append([ny, nx])
                shortest[ny][nx] = shortest[p[0]][p[1]] + 1
    return shortest[gy][gx]


# 全体の白いマスを数える
min_steps = dfs()
white_cnt = sum(line.count(".") for line in S)

print(white_cnt-min_steps-1)

Submission status: Wrong Answer

Solution code:
from queue import Queue
h,w=map(int,input().split())
S=[list(input()) for _ in range(h)]

memo=[[-1]*w for _ in range(h)]
def bfs(q):
  x,y,cnt=q.get()
  if x<0 or x>=w or y<0 or y>=h:
    return
  elif S[y][x]=='#':
    return
  elif memo[y][x]<0:
    memo[y][x]=cnt
    q.put([x-1,y,cnt+1])
    q.put([x+1,y,cnt+1])
    q.put([x,y-1,cnt+1])
    q.put([x,y+1,cnt+1])

q=Queue()
q.put([0,0,0])
while not q.empty():
  bfs(q)
cnt=0
for i in range(h):
  cnt+=S[i].count('.')
print(cnt-memo[h-1][w-1]-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
H, W = map(int, input().split())
L = []

for i in range(H):
  S = input()  
  L.append(list(1 if s == "." else 0 for s in S))
L = np.array(L)

Q = deque(())
Q.append((0,0))
while Q:
  i, j = Q.pop()
  if i == H-1 and j == W-1:
    print (np.sum(L) - (H + W -1))
    break
  if j != W-1:
    if L[i][j+1]:
      Q.append((i,j+1))
  if i != H-1:
    if L[i+1][j]:
      Q.append((i+1,j))
else:
  print (-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

cnt=0
for i in s:
    cnt+=i.count('.')

print(cnt)

sy,sx=0,0
gy,gx=h-1,w-1

dist=[[-1]*w for i in range(h)]
dist[sy][sx]=0

que=deque()
que.append((sy,sx))

while que:
    y,x=que.popleft()

    if y==gy and x==gx:
        print(dist[y][x])
        print(cnt-(dist[y][x]+1))
        exit()

    for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny=y+dy
        nx=x+dx
        if 0<=ny<=h-1 and 0<=nx<=w-1 and s[ny][nx]=='.' and dist[ny][nx]==-1:
            que.append((ny,nx))
            dist[ny][nx]=dist[y][x]+1

print(-1)

Submission status: Wrong Answer

Solution code:
#%%
def search(x, y, z):
    return [[x-1, y, z+1], [x, y-1, z+1], [x, y+1, z+1], [x+1, y, z+1]]
    
h, w = map(int, input().split())
s = [[] for _ in range(h)]
for i in range(h):
    s[i] = list(input())

sharp = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            sharp += 1

check = [[0] * w for _ in range(h)]
que = [[0,0,1]]
check[0][0] == 1
flag = False

while len(que) > 0:
    tmp = que.pop(-1)
    #print(tmp)
    for i in search(tmp[0], tmp[1], tmp[2]):
        if 0 <= i[0] <= h-1 and 0 <= i[1] <= w-1 and s[i[0]][i[1]] == '.':
            if check[i[0]][i[1]] == 0:
                que.append(i)
                check[i[0]][i[1]] = 1
    if tmp[0] == h-1 and tmp[1] == w-1:
        key = tmp[2]
        flag = True
        break
#print(key)

if check[0][0] =='#':
    flag = False

if flag:
    print(h*w - sharp - key)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
#%%
def search(x, y, z):
    return [[x-1, y, z+1], [x, y-1, z+1], [x, y+1, z+1], [x+1, y, z+1]]
    
h, w = map(int, input().split())
s = [[] for _ in range(h)]
for i in range(h):
    s[i] = list(input())

sharp = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            sharp += 1

check = [[0] * w for _ in range(h)]
que = [[0,0,1]]
check[0][0] == 1
flag = False

while len(que) > 0:
    tmp = que.pop(-1)
    #print(tmp)
    for i in search(tmp[0], tmp[1], tmp[2]):
        if 0 <= i[0] <= h-1 and 0 <= i[1] <= w-1 and s[i[0]][i[1]] == '.':
            if check[i[0]][i[1]] == 0:
                que.append(i)
                check[i[0]][i[1]] = 1
    if tmp[0] == h-1 and tmp[1] == w-1:
        key = tmp[2]
        flag = True
        break
#print(key)

if flag:
    print(h*w - sharp - key)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
#%%
def search(x, y, z):
    return [[x-1, y, z+1], [x, y-1, z+1], [x, y+1, z+1], [x+1, y, z+1]]
    
h, w = map(int, input().split())
s = [[] for _ in range(h)]
for i in range(h):
    s[i] = list(input())

sharp = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            sharp += 1

check = [[0] * w for _ in range(h)]
que = [[0,0,1]]
check[0][0] == 1
flag = False

while len(que) > 0:
    tmp = que.pop(-1)
   #print(tmp)
    for i in search(tmp[0], tmp[1], tmp[2]):
        if 0 <= i[0] <= h-1 and 0 <= i[1] <= w-1:
            if check[i[0]][i[1]] == 0:
                que.append(i)
                check[i[0]][i[1]] == 1
    if tmp[0] == h-1 and tmp[1] == w-1:
        key = tmp[2]
        flag = True
        break
#print(key)

if flag:
    print(h*w - sharp - key)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import collections

H,W=map(int,input().split())
S=[[10**10 for j in range(W)] for i in range(H)]

Q=collections.deque([])
S[0][0]=1

s=[]
cnt=0
for i in range(H):
  s=input()
  for j in range(W):
    if s[j]=="#":
      S[i][j]=-1
      cnt+=1
#print(S)

def bfs(i,j):
  if 0<=i+1<H and S[i][j]+1<S[i+1][j] and S[i+1][j]!=-1:
    Q.append([i+1,j])
    S[i+1][j]=S[i][j]+1
  if 0<=i-1<H and S[i][j]+1<S[i-1][j] and S[i-1][j]!=-1:
    Q.append([i-1,j])
    S[i-1][j]=S[i][j]+1
  if 0<=j+1<W and S[i][j]+1<S[i][j+1] and S[i][j+1]!=-1:
    Q.append([i,j+1])
    S[i][j+1]=S[i][j]+1
  if 0<=j-1<W and S[i][j]+1<S[i][j-1] and S[i][j-1]!=-1:
    Q.append([i,j-1])
    S[i][j-1]=S[i][j]+1

Q.append([0,0])
while len(Q):
  q=Q.popleft()
  bfs(q[0],q[1])
  #for i in range(H):
  #  print(S[i])
  #print("")
print(H*W-S[-1][-1]-cnt)