Problem p02579 (python)

Fixed submission:

import sys
from collections import deque
def main():
    movey = (0, -1, 0, 1)
    movex = (1, 0, -1, 0)
    warpy = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpx = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    dummy = tuple(['#'] * (w + 4))
    maze = {e: [] for e in range(h + 4)}
    maze[0] = dummy
    maze[1] = dummy
    for i in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze[i+2] = row
    maze[h+2] = dummy
    maze[h+3] = dummy
    maze[ch][cw] = 0
    maze[dh][dw] = 'g'

    nodes = deque()
    nodes.append((ch, cw))
    res = []
    while nodes:
        (n_y, n_x) = nodes.popleft()
        cur_masu = maze[n_y][n_x]
        flag = False
        for j1 in range(4):
            ny = n_y + movey[j1]
            nx = n_x + movex[j1]
            next_masu = maze[ny][nx]
            if next_masu == 'g':
                res.append(cur_masu)
            elif next_masu == '.':
                maze[ny][nx] = cur_masu
                nodes.appendleft((ny, nx))
            elif next_masu == '#':
                flag = True
            elif next_masu > cur_masu:
                maze[ny][nx] = cur_masu
                nodes.appendleft((ny, nx))
        if flag:
            for j1 in range(20):
                ny = n_y + warpy[j1]
                nx = n_x + warpx[j1]
                next_masu = maze[ny][nx]
                if next_masu == 'g':
                    res.append(cur_masu+1)
                elif next_masu == '.':
                    maze[ny][nx] = cur_masu + 1
                    nodes.append((ny, nx))
                elif next_masu == '#':
                    pass
                elif next_masu > cur_masu + 1:
                    maze[ny][nx] = cur_masu + 1
                    nodes.append((ny, nx))

    if res:
        print(min(res))
    else:
        print(-1)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
def main():
    movex = (1, 0, -1, 0)
    movey = (0, -1, 0, 1)
    warpx = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpy = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)

    def warp(cury2, curx2):
        curg2 = maze[cury2][curx2]
        nexts2 = []
        for j1 in range(20):
            nexty2 = cury2 + warpy[j1]
            nextx2 = curx2 + warpx[j1]
            nextg2 = maze[nexty2][nextx2]
            if nextg2 == 'g':
                print(curg2 + 1)
                sys.exit()
            elif nextg2 == '#':
                pass
            elif nextg2 == '.':
                maze[nexty2][nextx2] = curg2 + 1
                nexts2.append((nexty2, nextx2))
        return nexts2

    def dfs1(cury, curx):
        flag = False
        curg = maze[cury][curx]
        for i1 in range(4):
            nexty = cury + movey[i1]
            nextx = curx + movex[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(curg)
                sys.exit()
            elif nextg == '.':
                maze[nexty][nextx] = curg
                dfs1(nexty, nextx)
            elif nextg == '#':
                flag = True
        if flag:
            nexts = warp(cury, curx)
            if nexts:
                for ne in nexts:
                    dfs1(ne[0], ne[1])

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    dummy = ['#'] * (w + 4)
    maze = list()
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[ch][cw] = 0
    maze[dh][dw] = 'g'
    dfs1(ch, cw)
    print(-1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
def main():
    movex = (1, 0, -1, 0)
    movey = (0, -1, 0, 1)
    warpx = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpy = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)

    def dfs2(cury2, curx2):
        """
        for i1 in range(4):
            nexty = cur_coor[0] + movey[i1]
            nextx = cur_coor[1] + movex[i1]
            nextg = maze[nexty][nextx]
            if type(nextg) == int:
                if nextg < maze[cur_coor[0]][cur_coor[1]]:
                    maze[cur_coor[0]][cur_coor[1]] = nextg
        """
        curg2 = maze[cury2][curx2]
        for j1 in range(20):
            nexty2 = cury2 + warpy[j1]
            nextx2 = curx2 + warpx[j1]
            nextg2 = maze[nexty2][nextx2]
            if nextg2 == 'g':
                print(curg2 + 1)
                #print(*maze, sep='\n')
                sys.exit()
            elif nextg2 == '#':
                pass
            elif nextg2 == '.':
                maze[nexty2][nextx2] = curg2 + 1
                dfs1(nexty2, nextx2)
            elif type(nextg2) == int:
                if nextg2 > curg2 + 1:
                    maze[nexty2][nextx2] = curg2 + 1
                    dfs1(nexty2, nextx2)

    def dfs1(cury, curx):
        flag = False
        nexts = []
        curg = maze[cury][curx]
        for i1 in range(4):
            nexty = cury + movey[i1]
            nextx = curx + movex[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(curg)
                sys.exit()
            elif nextg == '.':
                maze[nexty][nextx] = curg
                nexts.append((nexty, nextx))
            elif nextg == '#':
                flag = True
            if type(nextg) == int:
                if nextg < curg:
                    maze[cury][curx] = nextg
                elif nextg > curg:
                    maze[nexty][nextx] = curg
                    nexts.append((nexty, nextx))
        if nexts:
            for ne in nexts:
                dfs1(ne[0], ne[1])
        if flag:
            dfs2(cury, curx)

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    dummy = ['#'] * (w + 4)
    maze = list()
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[ch][cw] = 0
    maze[dh][dw] = 'g'
    dfs1(ch, cw)
    print(-1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
def main():
    movex = (1, 0, -1, 0)
    movey = (0, -1, 0, 1)
    warpx = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpy = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)
    def dfs2(cury2, curx2):
        """
        for i1 in range(4):
            nexty = cur_coor[0] + movey[i1]
            nextx = cur_coor[1] + movex[i1]
            nextg = maze[nexty][nextx]
            if type(nextg) == int:
                if nextg < maze[cur_coor[0]][cur_coor[1]]:
                    maze[cur_coor[0]][cur_coor[1]] = nextg
        """
        curg2 = maze[cury2][curx2]
        for j1 in range(20):
            nexty2 = cury2 + warpy[j1]
            nextx2 = curx2 + warpx[j1]
            nextg2 = maze[nexty2][nextx2]
            if nextg2 == 'g':
                print(curg2 + 1)
                #print(*maze, sep='\n')
                sys.exit()
            elif nextg2 == '#':
                pass
            elif nextg2 == '.':
                maze[nexty2][nextx2] = curg2 + 1
                dfs1(nexty2, nextx2)
            elif type(nextg2) == int:
                if nextg2 > curg2 + 1:
                    maze[nexty2][nextx2] = curg2 + 1
                    dfs1(nexty2, nextx2)


    def dfs1(cury, curx):
        flag = False
        nexts = []
        curg = maze[cury][curx]
        for i1 in range(4):
            nexty = cury + movey[i1]
            nextx = curx + movex[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(curg)
                sys.exit()
            elif nextg == '.':
                maze[nexty][nextx] = curg
                nexts.append((nexty, nextx))
            elif nextg == '#':
                flag = True
            if type(nextg) == int:
                if nextg < curg:
                    maze[cury][curx] = nextg
                elif nextg > curg:
                    maze[nexty][nextx] = curg
                    nexts.append((nexty, nextx))
        for ne in nexts:
            dfs1(ne[0], ne[1])
        if flag:
            dfs2(cury, curx)


    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    dummy = ['#'] * (w + 4)
    maze = list()
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[ch][cw] = 0
    maze[dh][dw] = 'g'

    dfs1(ch, cw)
    print(-1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
def main():
    movex = (1, 0, -1, 0)
    movey = (0, -1, 0, 1)
    warpx = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpy = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)
    def dfs1(cury, curx):
        flag = False
        nexts = []
        curg = maze[cury][curx]
        for i1 in range(4):
            nexty = cury + movey[i1]
            nextx = curx + movex[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(curg)
                sys.exit()
            elif nextg == '.':
                maze[nexty][nextx] = curg
                nexts.append((nexty, nextx))
            elif nextg == '#':
                flag = True
            if type(nextg) == int:
                if nextg < curg:
                    maze[cury][curx] = nextg
                elif nextg > curg:
                    maze[nexty][nextx] = curg
                    nexts.append((nexty, nextx))
        for ne in nexts:
            dfs1(ne[0], ne[1])
        if flag:
            dfs2(cury, curx)

    def dfs2(cury2, curx2):
        """
        for i1 in range(4):
            nexty = cur_coor[0] + movey[i1]
            nextx = cur_coor[1] + movex[i1]
            nextg = maze[nexty][nextx]
            if type(nextg) == int:
                if nextg < maze[cur_coor[0]][cur_coor[1]]:
                    maze[cur_coor[0]][cur_coor[1]] = nextg
        """
        curg2 = maze[cury2][curx2]
        for j1 in range(20):
            nexty2 = cury2 + warpy[j1]
            nextx2 = curx2 + warpx[j1]
            nextg2 = maze[nexty2][nextx2]
            if nextg2 == 'g':
                print(curg2 + 1)
                #print(*maze, sep='\n')
                sys.exit()
            elif nextg2 == '#':
                pass
            elif nextg2 == '.':
                maze[nexty2][nextx2] = curg2 + 1
                dfs1(nexty2, nextx2)
            elif type(nextg2) == int:
                if nextg2 > curg2 + 1:
                    maze[nexty2][nextx2] = curg2 + 1
                    dfs1(nexty2, nextx2)

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    dummy = ['#'] * (w + 4)
    maze = list()
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[ch][cw] = 0
    maze[dh][dw] = 'g'

    dfs1(ch, cw)
    print(-1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
def main():
    movex = (1, 0, -1, 0)
    movey = (0, -1, 0, 1)
    warpx = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpy = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)
    def dfs1(cur_coor):
        flag = False
        nexts = []
        curg = maze[cur_coor[0]][cur_coor[1]]
        for i1 in range(4):
            nexty = cur_coor[0] + movey[i1]
            nextx = cur_coor[1] + movex[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(curg)
                sys.exit()
            elif nextg == '.':
                maze[nexty][nextx] = curg
                nexts.append((nexty, nextx))
            elif nextg == '#':
                flag = True
            if type(nextg) == int:
                if nextg < curg:
                    maze[cur_coor[0]][cur_coor[1]] = nextg
                elif nextg > curg:
                    maze[nexty][nextx] = curg
                    nexts.append((nexty, nextx))
        for ne in nexts:
            dfs1(ne)
        if flag:
            dfs2(cur_coor)

    def dfs2(cur_coor):
        """
        for i1 in range(4):
            nexty = cur_coor[0] + movey[i1]
            nextx = cur_coor[1] + movex[i1]
            nextg = maze[nexty][nextx]
            if type(nextg) == int:
                if nextg < maze[cur_coor[0]][cur_coor[1]]:
                    maze[cur_coor[0]][cur_coor[1]] = nextg
        """
        curg2 = maze[cur_coor[0]][cur_coor[1]]
        for j1 in range(20):
            nexty2 = cur_coor[0] + warpy[j1]
            nextx2 = cur_coor[1] + warpx[j1]
            nextg2 = maze[nexty2][nextx2]
            if nextg2 == 'g':
                print(curg2 + 1)
                sys.exit()
            elif nextg2 == '#':
                pass
            elif nextg2 == '.':
                maze[nexty2][nextx2] = curg2 + 1
                dfs1((nexty2, nextx2))
            elif type(nextg2) == int:
                if nextg2 > curg2 + 1:
                    maze[nexty2][nextx2] = curg2 + 1
                    dfs1((nexty2, nextx2))

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    dummy = ['#'] * (w + 4)
    maze = list()
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[ch][cw] = 0
    maze[dh][dw] = 'g'

    dfs1((ch, cw))
    print(-1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
def main():
    movex = (1, 0, -1, 0)
    movey = (0, -1, 0, 1)
    warpx = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpy = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)
    def dfs1(cur_coor):
        flag = False
        nexts = []
        for i1 in range(4):
            nexty = cur_coor[0] + movey[i1]
            nextx = cur_coor[1] + movex[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(maze[cur_coor[0]][cur_coor[1]])
                sys.exit()
            elif nextg == '.':
                maze[nexty][nextx] = maze[cur_coor[0]][cur_coor[1]]
                nexts.append((nexty, nextx))
            elif nextg == '#':
                flag = True
            if type(nextg) == int:
                if nextg < maze[cur_coor[0]][cur_coor[1]]:
                    maze[cur_coor[0]][cur_coor[1]] = nextg
                elif nextg > maze[cur_coor[0]][cur_coor[1]]:
                    maze[nexty][nextx] = maze[cur_coor[0]][cur_coor[1]]
                    nexts.append((nexty, nextx))
        for ne in nexts:
            dfs1(ne)
        if flag:
            dfs2(cur_coor)

    def dfs2(cur_coor):
        """
        for i1 in range(4):
            nexty = cur_coor[0] + movey[i1]
            nextx = cur_coor[1] + movex[i1]
            nextg = maze[nexty][nextx]
            if type(nextg) == int:
                if nextg < maze[cur_coor[0]][cur_coor[1]]:
                    maze[cur_coor[0]][cur_coor[1]] = nextg
        """
        for j1 in range(20):
            nexty = cur_coor[0] + warpy[j1]
            nextx = cur_coor[1] + warpx[j1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(maze[cur_coor[0]][cur_coor[1]] + 1)
                sys.exit()
            elif nextg == '#':
                pass
            elif nextg == '.':
                maze[nexty][nextx] = maze[cur_coor[0]][cur_coor[1]] + 1
                dfs1((nexty, nextx))
            elif maze[nexty][nextx] > maze[cur_coor[0]][cur_coor[1]] + 1:
                maze[nexty][nextx] = maze[cur_coor[0]][cur_coor[1]] + 1
                dfs1((nexty, nextx))

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    dummy = ['#'] * (w + 4)
    maze = list()
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[ch][cw] = 0
    maze[dh][dw] = 'g'

    dfs1((ch, cw))
    print(-1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():

    movex = (1, 0, -1, 0)
    movey = (0, -1, 0, 1)
    warpx = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpy = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)
    def dfs1(cur_coor):
        for i1 in range(4):
            nextx = cur_coor[1] + movex[i1]
            nexty = cur_coor[0] + movey[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                print(0)
                sys.exit()
            elif nextg == '.':
                maze[nexty][nextx] = '-'
                dfs1((nexty, nextx))
            else:
                pass
    def dfs1a(cur_coor):
        for i1 in range(4):
            nextx = cur_coor[1] + movex[i1]
            nexty = cur_coor[0] + movey[i1]
            nextg = maze[nexty][nextx]
            if nextg == '.':
                maze[nexty][nextx] = '!'
                dfs1((nexty, nextx))
            else:
                pass
    def dfs2(cur_coor, r):
        for j1 in range(20):
            nextx = cur_coor[1] + warpx[j1]
            nexty = cur_coor[0] + warpy[j1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                rs.append(r + 1)
                return
            elif nextg == '.' or nextg == '-':
                maze[nexty][nextx] = '+'
                dfs2((nexty, nextx), r + 1)
            else:
                pass

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    dummy = ['#'] * (w + 4)
    maze = []
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[dh][dw] = 'g'

    dfs1((ch, cw))
    #dfs1a((dh, dw))
    rs = []
    dfs2((ch, cw) ,0)
    if rs:
        print(min(rs))
    else:
        print(-1)


if __name__ == '__main__':
    main()