Problem p03436 (python)

Fixed submission:
from sys import stdin
import collections
from sys import  setrecursionlimit
setrecursionlimit(30000)

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[0]<0 or new_pos[0]>=H or new_pos[1]<0 or new_pos[1]>=W:
                continue
            if new_pos[:2] in visited:
                continue
            if data[new_pos[0]][new_pos[1]]==".":
#            if True:
                candidates.append(new_pos)
    
    while(True):
        if len(candidates)==0:
            return -1
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Buggy submission (verdict: Runtime Error):
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[0]<0 or new_pos[0]>=H or new_pos[1]<0 or new_pos[1]>=W:
                continue
            if new_pos[:2] in visited:
                continue
            if data[new_pos[0]][new_pos[1]]==".":
#            if True:
                candidates.append(new_pos)
    
    while(True):
        if len(candidates)==0:
            return -1
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Buggy submission (verdict: Runtime Error):
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[0]<0 or new_pos[0]>=H or new_pos[1]<0 or new_pos[1]>=W:
                continue
            if new_pos[:2] in visited:
                continue
            if data[new_pos[0]][new_pos[1]]==".":
#            if True:
                candidates.append(new_pos)
    
    if len(candidates)==0:
        return -1
    while(True):
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        if len(candidates)==0:
            return -1
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Buggy submission (verdict: Runtime Error):
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[0]<0 or new_pos[0]>=H or new_pos[1]<0 or new_pos[1]>=W:
                continue
            if new_pos[:2] in visited:
                continue
            if data[new_pos[0]][new_pos[1]]==".":
#            if True:
                candidates.append(new_pos)
    
    while(True):
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        if len(candidates)==0:
            return -1
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Buggy submission (verdict: Runtime Error):
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[0]<0 or new_pos[0]>=H or new_pos[1]<0 or new_pos[1]>=W:
                continue
            if new_pos[:2] in visited:
                continue
#            if data[new_pos[0]][new_pos[1]]!="#":
            if True:
                candidates.append(new_pos)
    
    while(True):
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        if len(candidates)==0:
            return -1
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Buggy submission (verdict: Runtime Error):
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()
print(data)

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[0]<0 or new_pos[0]>=H or new_pos[1]<0 or new_pos[1]>=W:
                continue
            if new_pos[:2] in visited:
                continue
#            if data[new_pos[0]][new_pos[1]]!="#":
            if True:
                candidates.append(new_pos)
    
    while(True):
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        if len(candidates)==0:
            return -1
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Buggy submission (verdict: Runtime Error):
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[0]<0 or new_pos[0]>=H or new_pos[1]<0 or new_pos[1]>=W:
                continue
            if new_pos[:2] in visited:
                continue
            try:
                if data[new_pos[0]][new_pos[1]]!="#":
                    candidates.append(new_pos)
            except:
                continue
                
    
    while(True):
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        if len(candidates)==0:
            return -1
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Buggy submission (verdict: Runtime Error):
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[0]<0 or new_pos[0]>=H or new_pos[1]<0 or new_pos[1]>=W:
                continue
            if new_pos[:2] in visited:
                continue
            try:
                if data[new_pos[0]][new_pos[1]]!="#":
                    candidates.append(new_pos)
                
    
    while(True):
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        if len(candidates)==0:
            return -1
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Buggy submission (verdict: Runtime Error):
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            if start_pos[0]+i<0 or start_pos[0]+i>=H or start_pos[1]+j<0 or start_pos[1]+j>=W:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[:2] in visited:
                continue
            if data[new_pos[0]][new_pos[1]]!="#":
                candidates.append(new_pos)
    
    while(True):
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        if len(candidates)==0:
            return -1
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Buggy submission (verdict: Runtime Error):
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            if start_pos[0]+i<0 or start_pos[0]+i>=H or start_pos[1]+j<0 or start_pos[1]+j>=W:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[:2] in visited:
                continue
            candidates.append(new_pos)
    
    while(True):
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        if len(candidates)==0:
            return -1
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
if result==-1:
    print(-1)
else:
    print(check_number(data)-result-1)

Buggy submission (verdict: Runtime Error):
from sys import stdin
import collections

[H, W] = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for line in range(H):
    temp = stdin.readline().rstrip()
    temp_arr = []
    for j in range(len(temp)):
        temp_arr.append(temp[j])
    data.append(temp_arr)


#幅優先探索で最短経路を探す

visited = []
candidates = collections.deque()

def wfs(data, start_pos, visited, candidates):
    index = start_pos[2]
    visited.append([start_pos[0],start_pos[1]])

    #goal
    if start_pos[0] == H-1 and start_pos[1] == W-1:
        return start_pos[2]
    
    #candidates
    for i in range(-1,2):
        for j in range(-1,2):
            if abs(i)+ abs(j)!=1:
                continue
            if start_pos[0]+i<0 or start_pos[0]+i>=H or start_pos[1]+j<0 or start_pos[1]+j>=W:
                continue
            new_pos = [start_pos[0]+i, start_pos[1]+j,index+1]
            if new_pos[:2] in visited:
                continue
            candidates.append(new_pos)
    
    while(True):
        next_pos = candidates.popleft()
        if next_pos[:2] not in visited:
            break
        if len(candidates)==0:
            return -1
        
    result = wfs(data, next_pos, visited,candidates)

    return result

def check_number(data):
    count = 0
    for i in range(H):
        for j in range(W):
            if data[i][j]==".":
                count+=1
    return count


result = wfs(data,[0,0,0],visited, candidates)
print(check_number(data)-result-1)