[백준 17836] 공주님을 구해라

def maze(M,m,n,p,q):

    a=[]

    b=set()

    a.append([(p,q)])

    b.add((p,q))

    k=0

    if (1,1)==(p,q):

        return 0

    

    d=set()

    while (1,1)!=(m,n):

        d=set()

        for i in range(len(a[k])):

            if 0<a[k][i][0]-1<=m:

                if M[a[k][i][0]-2][a[k][i][1]-1]=='1' and ((a[k][i][0]-1,a[k][i][1]) in b)==False:

                    b.add((a[k][i][0]-1,a[k][i][1]))

                    d.add((a[k][i][0]-1,a[k][i][1]))

            if 0<a[k][i][1]-1<=n:

                if M[a[k][i][0]-1][a[k][i][1]-2]=='1' and ((a[k][i][0],a[k][i][1]-1) in b)==False:

                    b.add((a[k][i][0],a[k][i][1]-1))

                    d.add((a[k][i][0],a[k][i][1]-1))

            if 0<a[k][i][0]+1<=m:

                if M[a[k][i][0]][a[k][i][1]-1]=='1' and ((a[k][i][0]+1,a[k][i][1]) in b)==False:

                    b.add((a[k][i][0]+1,a[k][i][1]))

                    d.add((a[k][i][0]+1,a[k][i][1]))

            if 0<a[k][i][1]+1<=n:

                if M[a[k][i][0]-1][a[k][i][1]]=='1' and ((a[k][i][0],a[k][i][1]+1) in b)==False:

                    b.add((a[k][i][0],a[k][i][1]+1))

                    d.add((a[k][i][0],a[k][i][1]+1))

        a.append(list(d))

        k+=1

        if ((1,1) in d)==True:

            return k

        if k==n*m+1:

            return -1

m,n,t=map(int, input().split())

M=[input().replace(" ","") for _ in range(m)]

N=[]

 

for i in range(m):

    if M[i].find("2")!=-1:

        p=i+1

        q=M[i].find("2")+1

    temp=M[i].replace("0","2")

    temp=temp.replace("1","0")

    temp=temp.replace("2","1")

    N.append(temp)

 

alpha=maze(N,m,n,m,n)

beta=maze(N,m,n,p,q)

gamma=m+n-p-q

 

if alpha<0 and beta>=0:

    if beta+gamma<=t:

        print(beta+gamma)

    else:

        print("Fail")    

elif alpha<0 and beta<0:

    print("Fail")

elif alpha>=0 and beta<0:

    if alpha<=t:

        print(alpha)

    else:

        print("Fail")

else :

    if min(alpha,beta+gamma)<=t:

        print(min(alpha,beta+gamma))

    else:

        print("Fail")