Problem p03436 (python)

Fixed submission:
from collections import deque

def bfs(maze,visited,sy,sx,gy,gx):
    Step = ([1,0],[0,1],[-1,0],[0,-1])
    
    que = deque([[sx,sy]])
    visited[sx][sy] = 1
    
    while que:
        y,x = que.popleft()
        if [y,x] == [gy,gx]:
            return visited[y][x]
        for j,k in Step:
            ny,nx = y+j , x+k
            if 0 <= ny <= gy and 0 <= nx <= gx:
                if maze[ny][nx] == '.' and visited[ny][nx] == INF:
                    visited[ny][nx] = visited[y][x] + 1
                    que.append([ny,nx])


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

cntSharp = 0
for i in range(h):
    cntSharp += maze[i].count('.')

INF = 10**5
visited = [[INF]*w for _ in range(h)]

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

minStep = bfs(maze,visited,sy,sx,gy,gx)
print(cntSharp - minStep if visited[gy][gx] != INF else -1)

Buggy submission (verdict: Runtime Error):

from collections import deque

w,h = map(int,input().split())
maze = []

cnt_wall = 0
for _ in range(h):
    s = input()
    cnt_wall += s.count('#')
    maze.append(s)

inf = 10**5
def  bfs(d):
    visited = [[inf]*w for _ in range(h)]
    sx,sy = 0,0
    gx,gy = w-1, h-1
    que = deque([(sx,sy)])
    visited[sx][sy] = 1
    
    while que:
        x,y = que.popleft()
        if x==gx and y==gy:
            return visited[x][y]
        for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
            nx,ny = x+i, y+j
            if 0<=nx<=gx and 0<=ny<=gy:
                if d[nx][ny]=='.' and visited[nx][ny]==inf:
                    visited[nx][ny] = visited[x][y]+1
                    que.append((nx,ny))
    else:
        return inf

min_step = bfs(maze)
if min_step == inf:
    print(-1)
else:
    print(h*w - min_step - cnt_wall)

Buggy submission (verdict: Runtime Error):

from collections import deque

h,w = map(int,input().split())
maze = []

cnt_wall = 0
for _ in range(h):
    s = input()
    cnt_wall += s.count('#')
    maze.append(s)

inf = 10**5
def  bfs(d):
    visited = [[inf]*w for _ in range(h)]
    sx,sy = 0,0
    gx,gy = w-1, h-1
    que = deque([(sx,sy)])
    visited[sx][sy] = 1
    
    while que:
        x,y = que.popleft()
        if x==gx and y==gy:
            return visited[gx][gy]
        for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
            nx,ny = x+i, y+j
            if 0<=nx<=gx and 0<=ny<=gy:
                if d[nx][ny]=='.' and visited[nx][ny]==inf:
                    visited[nx][ny] = visited[x][y]+1
                    que.append((nx,ny))
    else:
        return inf

min_step = bfs(maze)
if min_step == inf:
    print(-1)
else:
    print(h*w - min_step - cnt_wall)

Buggy submission (verdict: Runtime Error):

from collections import deque

h,w = map(int,input().split())
maze = []

cnt_wall = 0
for _ in range(h):
    s = input()
    cnt_wall += s.count('#')
    maze.append(s)

def  bfs(d):
    inf = 10**5
    visited = [[inf]*w for _ in range(h)]
    sx,sy = 0,0
    gx,gy = w-1, h-1
    que = deque([(sx,sy)])
    visited[sx][sy] = 1
    
    while que:
        x,y = que.popleft()
        if x==gx and y==gy:
            return visited[gx][gy]
        for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
            nx,ny = x+i, y+j
            if 0<=nx<=gx and 0<=ny<=gy:
                if d[nx][ny]=='.' and visited[nx][ny] == inf:
                    visited[nx][ny] = visited[x][y]+1
                    que.append((nx,ny))



min_step = bfs(maze)
if min_step == 10**5:
    print(-1)
else:
    print(h*w - min_step - cnt_wall)

Buggy submission (verdict: Runtime Error):

from collections import deque

h,w = map(int,input().split())
maze = []

cnt_wall = 0
for _ in range(h):
    s = input()
    cnt_wall += s.count('#')
    maze.append(s)


def bfs(d):
    que = deque([(0,0,1)])
    visited = [[False]*w for _ in range(h)]
    table = [[-1]*w for _ in range(h)]
    while que:
        x,y,cnt = que.popleft()
        visited[x][y] = True
        table[x][y] = cnt
        for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
            nx,ny = x+i,y+j
            if 0<=nx<w and 0<=ny<h:
                if (visited[nx][ny] == False):
                    if (d[nx][ny]=='.'):
                        que.append((nx, ny,cnt+1))
    return table[h-1][w-1]


min_step = bfs(maze)
if min_step < 0:
    print(-1)
else:
    print(h*w - min_step - cnt_wall)

Buggy submission (verdict: Runtime Error):
from collections import deque

def bfs(maze,visited,sy,sx,gy,gx):
    Step = ([1,0],[0,1],[-1,0],[0,-1])
    
    que = deque([[sx,sy]])
    visited[sx][sy] = 1
    
    while que:
        y,x = que.popleft()
        if [y,x] == [gy,gx]:
            return visited[y][x]
        for j,k in Step:
            ny,nx = y+j , x+k
            if 0 <= ny <= gy and 0 <= nx <= gx:
                if maze[ny][nx] == '.' and visited[ny][nx] == INF:
                    visited[ny][nx] = visited[y][x] + 1
                    que.append([ny,nx])


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

cntSharp = 0
for i in range(h):
    cntSharp += maze[i].count('.')

INF = 10**5
visited = [[INF]*w for _ in range(h)]

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

minStep = bfs(maze,visited,sy,sx,gy,gx)
print(cntSharp - minStep)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**6)
from collections import deque
from itertools import chain

def bfs(maze,visited,gy,gx):
    que = deque([[0,0]])
    visited[0][0] = 0
    
    while que:
        y,x = que.popleft()
        if [y,x] == [gy,gx]:
            return visited[y][x]
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx = y+j,x+k
            if 0 <= ny < w and 0 <= nx < h:
                if maze[ny][nx] == "." and visited[ny][nx] == -1:
                    visited[ny][nx] = visited[y][x] + 1
                    que.append([ny,nx])

h,w = map(int,input().split())
maze = [input() for _ in range(h)]
visited = [[-1]*(w) for _ in range(h)]
sr = bfs(maze,visited,h-1,w-1)

num_dot = list(chain.from_iterable(maze))
num_dot = num_dot.count('.')

if sr == -1 or num_dot < sr:
    print(-1)
else:
    print(num_dot - sr - 1)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**6)
from collections import deque
from itertools import chain

def bfs(maze,visited,gy,gx):
    que = deque([[0,0]])
    visited[0][0] = 0
    
    while que:
        y,x = que.popleft()
        if [y,x] == [gy,gx]:
            return visited[y][x]
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx = y+j,x+k
            if 0 <= ny < w and 0 <= nx < h:
                if maze[ny][nx] == "." and visited[ny][nx] == -1:
                    visited[ny][nx] = visited[y][x] + 1
                    que.append([ny,nx])

h,w = map(int,input().split())
maze = [input() for _ in range(h)]
visited = [[-1]*(w) for _ in range(h)]
sr = bfs(maze,visited,h-1,w-1)

num_dot = list(chain.from_iterable(maze))
num_dot = num_dot.count('.')
print(num_dot - sr - 1)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**6)

from collections import deque
from itertools import chain

def bfs(maze,visited,gy,gx):
    que = deque([[1,1]])
    visited[1][1] = 0
    
    while que:
        y,x = que.popleft()
        if [y,x] == [gy,gx]:
            return visited[y][x]
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx = y+j,x+k
            if maze[ny][nx] == "." and visited[ny][nx] == -1:
                visited[ny][nx] = visited[y][x] + 1
                que.append([ny,nx])

h,w = map(int,input().split())
maze = ["#"*(w+2)] + ["#"+input()+"#" for _ in range(h)] + ["#"*(w+2)]
visited = [[-1]*(w+2) for _ in range(h+2)]
sr = bfs(maze,visited,h,w)

num_dot = list(chain.from_iterable(maze))
num_dot = num_dot.count('.')
print(num_dot - sr - 1)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**8)

from collections import deque
from itertools import chain

def bfs(maze,visited,gy,gx):
    que = deque([[1,1]])
    visited[1][1] = 0
    
    while que:
        y,x = que.popleft()
        if [y,x] == [gy,gx]:
            return visited[y][x]
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx = y+j,x+k
            if maze[ny][nx] == "." and visited[ny][nx] == -1:
                visited[ny][nx] = visited[y][x] + 1
                que.append([ny,nx])

h,w = map(int,input().split())
maze = ["#"*(w+2)] + ["#"+input()+"#" for _ in range(h)] + ["#"*(w+2)]
visited = [[-1]*(w+2) for _ in range(h+2)]
sr = bfs(maze,visited,h,w)

num_dot = list(chain.from_iterable(maze))
num_dot = num_dot.count('.')
num_sharp = h*w - num_dot
print(h*w - num_sharp - sr - 1)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**6)

from collections import deque
from itertools import chain

def bfs(maze,visited,gy,gx):
    que = deque([[1,1]])
    visited[1][1] = 0
    
    while que:
        y,x = que.popleft()
        if [y,x] == [gy,gx]:
            return visited[y][x]
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx = y+j,x+k
            if maze[ny][nx] == "." and visited[ny][nx] == -1:
                visited[ny][nx] = visited[y][x] + 1
                que.append([ny,nx])

h,w = map(int,input().split())
maze = ["#"*(w+2)] + ["#"+input()+"#" for _ in range(h)] + ["#"*(w+2)]
visited = [[-1]*(w+2) for _ in range(h+2)]
sr = bfs(maze,visited,h,w)

num_dot = list(chain.from_iterable(maze))
num_dot = num_dot.count('.')
num_sharp = h*w - num_dot
print(h*w - num_sharp - sr - 1)

Buggy submission (verdict: Runtime Error):
from collections import deque
from itertools import chain

def bfs(maze,visited,gy,gx):
    que = deque([[1,1]])
    visited[1][1] = 0
    
    while que:
        y,x = que.popleft()
        if [y,x] == [gy,gx]:
            return visited[y][x]
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx = y+j,x+k
            if maze[ny][nx] == "." and visited[ny][nx] == -1:
                visited[ny][nx] = visited[y][x] + 1
                que.append([ny,nx])

h,w = map(int,input().split())
maze = ["#"*(w+2)] + ["#"+input()+"#" for _ in range(h)] + ["#"*(w+2)]
visited = [[-1]*(w+2) for _ in range(h+2)]
sr = bfs(maze,visited,h,w)

num_dot = list(chain.from_iterable(maze))
num_dot = num_dot.count('.')
num_sharp = h*w - num_dot
print(h*w - num_sharp - sr - 1)

Buggy submission (verdict: Runtime Error):
from collections import deque
from itertools import chain

def bfs(maze,visited,gy,gx):
    que = deque([[1,1]])
    visited[1][1] = 0
    
    while que:
        y,x = que.popleft()
        if [y,x] == [gy,gx]:
            return visited[y][x]
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx = y+j,x+k
            if maze[ny][nx] == "." and visited[ny][nx] == -1:
                visited[ny][nx] = visited[y][x] + 1
                que.append([ny,nx])

h,w = map(int,input().split())
maze = ["#"*(w+2)] + ["#"+input()+"#" for _ in range(h)] + ["#"*(w+2)]
visited = [[-1]*(w+2) for _ in range(h+2)]
sr = bfs(maze,visited,h,w)

num_dot = list(chain.from_iterable(maze))
num_dot = num_dot.count('.')
num_sharp = h*w - num_dot
print(h*w - num_sharp - sr - 1)