请教C语言编程高手帮助：猫捉老鼠问题

Question

一只猫和一只老鼠在10*10的迷宫中。迷宫中的每个方格可以是空的，或者含有障碍。猫和老鼠可以进入任意一个空的方格中。当他们相遇时，猫和老鼠在同一个方格中。但是，无论猫或老鼠都不能进入有障碍的方格。老鼠在迷宫中按照一种固定的方式行走：每个时刻，老鼠都向它所面对的方向前进一格，这需要花费1秒时间。如果前方是一个障碍或者是迷宫的边界，它将花1秒的时间按顺时针方向转90度。为了抓到老鼠，这只猫决定也按照与老鼠相同的行走方式行进。初始时，猫和老鼠不会在同一个方格中。并且它们都面向北方。你的任务是编一个程序，求出猫捉到老鼠的所花时间。
要求：
（1）输入数据的第一行n，表示输入数据的组数。每组数据由10行组成，每行10个字符，表示迷宫的地图以及猫和老鼠的初始位置。输入数据保证只有一只猫和一只老鼠。每组输入数据之后均有一个空行作为间隔。
（2）对于每组给定的输入，输出一行仅含一个数，即猫捉到老鼠所花的时间。如果猫永远都无法抓到老鼠，则输出0。

Answer 1

这其实就是迷宫问题的变体，猫最初的位置是入口，老鼠的位置就是出口，只不过这个出口处于不停的变动当中，但是老鼠的逃跑方式已经确定，所以只管让它走，猫捉老鼠就是一个求解迷宫路径的过程。比较麻烦的就猫永远抓不到老鼠的情况该如何判定，我们可以利用两个栈把猫和老鼠的路径都保存起来，并且标上序号，因为不用打印最短路径所以就不必出栈，每当猫或老鼠走一步的时候就遍历两个栈，如果猫和老鼠走到他们某一次都走过的地方那么就表明他们将永远在这段路径中循环，即猫永远抓不到老鼠。比如老鼠第10步走到（10,11），猫第十步走到（20,21），而老鼠第30步又走到（10,11），猫第30步也走到（20,21）就表明猫和老鼠会在这段路程中循环不息。我的思路就是这样吧，如果有什么不对请帮忙指点一下，代码有时间我也去打打，如果你做出来了不妨交流一下，呵呵！追问

就是 因为不会做啊 才请教的 呵呵呵 那个永远不会追上的 判断 的确有点麻烦
还有就是 那个 固定方向移动 该怎么解决

追答

我补充一下，刚才说的不太全，应该是当猫和老鼠在同一时间它们的状态又回到之前某一时刻的状态，而不是在某一步回到某一步所在的位置。如果老鼠第10秒走到（10,8）朝南，猫第十秒追到（8,2）朝北；老鼠第20秒又走到（10,8）还是朝南（方向必须和第十秒一致），猫第20秒又追到（8,2）方向仍然朝北，如果再这个过程中猫没有追到老鼠那么就永远都追不上，它们将永远在这个路线中来回转悠。
关于方向移动，跟迷宫问题很像，可以定义一个结构
typedef struct{
int x;//x坐标
int y; //y坐标
DIR di;//方位} POS;
方位di用枚举型
typedef enum{EAST,SOUTH,WEST,NORTH} DIR;
每移动一次方向就di自加一次（如果是turbo c可以不管di是否大于NORTH即3，该编译器会在大于最大值是回到最小值，但是VC好像不能，所以如果用VC最好判断一下di是否大于NORTH如果大于则赋值为EAST）；

3----追赶
老鼠先走，每走一步时间time自加1秒，其中转身也算一步，每走一步将其当前位置入栈MOUTHPATH，定义栈的元素结构如下：
typedef struct{
POS pos; //位置
int tm; //时间};
每走一步tm加1，不妨直接用time直接赋给它。
然后猫追，猫追的时候time就没必要自加了，因为转身和追赶一次都花一秒。然后将time赋值给猫的路径，入栈CATPATH；检测是否追上，如果没追上再检测是否追的上，如此循环即可。如果还有问题我们百度Hi讨论吧。

追问

那个 是否追赶上的 判断 怎么用C来实现呢 我比较笨 不太懂

追答

弄了大半天总算有眉目了，可是不知道怎么搞的realloc好像很喜欢惹麻烦