问题 G: 四连通迷宫（Python）

题目描述

设定一个M*M（2≤M≤9）的迷宫结构，其中0代表可通行区域，1代表障碍物。
迷宫的起点位于左上角，终点位于右上角，起点与终点均被标记为0。
在该迷宫中，移动方向仅限于上、下、左、右四个方位。若所到达的格子数值为0，则表示可以通行；若为1，则表示存在障碍物，无法通过，需另寻其他路径。
要求计算从起点至终点的所有可行路径数量（路径不可重复），并输出总数。如果起点无法抵达终点，则输出0。

输入

第一行需输入一个正整数M（范围为≤M≤9），用于表示迷宫的行数与列数均为M。
从第二行至第n+1行，依次给出一个M阶的由0和1组成的方阵。

小标题

计算从入口至出口的所有不重复路径，并输出路径的总数量。若入口无法抵达出口，则应返回0。

样例输入 Copy

3
0 0 0
1 0 1
0 0 1

样例输出 Copy

1

    #4联通迷宫
    n = int(input())
    mp=[]   #创建一个空的二维列表用来存放迷宫
    for i in range(n):
    a = list(map(int,input().split()))
    mp.append(a) #创建迷宫
    dir = [(-1,0),(1,0),(0,-1),(0,1)] #需要