링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

해설

탈주범은 정해진 위치에서 1초에 시작하며 효율성을 올리기위해 check[시간][x좌표][y좌표]에 해당 시간의 좌표 마킹을 통해 중복으로 방문하는 것을 막으면서 부르트포스 알고리즘으로 풀면된다.

cnum = int(input())
move = [
    [0,0,0,0],
    [1,1,1,1],
    [1,0,1,0],
    [0,1,0,1],
    [1,1,0,0],
    [0,1,1,0],
    [0,0,1,1],
    [1,0,0,1]
     ]
#상 우 하 좌    
dx=[-1,0,1,0]
dy=[0,1,0,-1]

def BF(x,y,cnt):
    global answer
    
    #print(x,y,cnt)
    if time<cnt:
        return
    if check[cnt][x][y]!=0:
        return
    
    if cnt==time :
        if check[cnt][x][y]==0:
            #print(x,y)
            answer +=1
            check[cnt][x][y]=1
        return
    check[cnt][x][y]=1
    BF(x,y,cnt+1)
    
    
    nmove = move[board[x][y]]

    for i in range(4):
        if nmove[i]==1:
            nx = dx[i]+x
            ny = dy[i]+y
            if 0<=nx<h and 0<=ny<w:
                #상 우 하 좌
                #위 아래
                if i==0 and move[board[nx][ny]][2]==1:
                    BF(nx,ny,cnt+1)
                #우 좌
                if i==1 and move[board[nx][ny]][3]==1:
                    BF(nx,ny,cnt+1)
                #아래 위
                if i==2 and move[board[nx][ny]][0]==1:
                    BF(nx,ny,cnt+1)
                #좌 우    
                if i==3 and move[board[nx][ny]][1]==1:
                    BF(nx,ny,cnt+1)

for case in range(1,cnum+1):
    h,w,sh,sw,time = map(int,input().split())
    board = [ list(map(int,input().split())) for _ in range(h)]
    check = [[[0 for _ in range(w)] for _ in range(h)] for _ in range(time+1)]
    answer = 0
    BF(sh,sw,1)
    print(f"#{case} {answer}")
    #상 우 하 좌

'''
1            
5 6 2 1 3      
0 0 5 3 6 0
0 0 2 0 2 0
3 3 1 3 7 0
0 0 0 0 0 0
0 0 0 0 0 0
'''