问题描述
一只老鼠被放到了一个迷宫里。迷宫里的某处有一块大奶酪。
该迷宫以一个二维整数数组表示,0表示墙,1表示小老鼠可以通过的路径,9表示那一大块奶酪。小老鼠从左上角0, 0位置出发。
请编写一个函数isPath来确定小老鼠是否可以吃到那一大块奶酪。isPath的输入包括:一个代表迷宫矩阵的二维数组grid,和矩阵的维数m,n。
如果小老鼠和奶酪之间存在一条路径,则函数返回 1;否则返回0。小老鼠不能离开迷宫或翻墙。
解决思路
根据输入矩阵构造树，树的每个节点非零，边构造边检测。假设输入矩阵是：
1 1 0 0 0 0 0 1
1 1 1 1 1 1 1 1
1 0 0 0 1 0 0 1
1 1 1 0 1 0 0 1
0 1 0 0 1 1 1 1
0 1 0 0 0 0 0 1
0 1 0 9 1 1 1 1
0 1 1 1 0 0 1 0
那么该树的结构如下：(其中节点上的数据为该节点在矩阵中的坐标)
容易知道(6,3)为9，即存在路径，且最短步数为11。