No.0020-CareerCup

问题描述

Given an MxN matrix, determine whether a path can be drawn through every node in the matrix such that the end node is next to the start node, and each node is only touched once.
给一个MxN的矩阵，问能不能找到一条一笔画的路径，能不重复地通过每个节点而且开始和结束的点相邻。

信息补全

好像没什么需要询问补充的。

问题分析

1x1的时候因为没有结束点，因此是不符合要求的。

暴力破解

完全不管三七二十一，就用程序来模拟。
那么首先是要选择出发点吧，有MxN种选择。
然后是生成路径，可以考虑BFS或者DFS。
在无路可走的时候判断一下是不是走完了，以及是不是和初始点相邻。
此外还可以每一步判断一下初始点周围还有没有位置。
不过总的来说时间复杂度非常高。

观察法

其实这个题更多是智力向或者数学向，观察归纳会比较有效。假设N>0.

• 1xN
  这种情况，只有1x2是符合条件的。但其实还是托了那个2的福。
• 2xN
  这种情况都符合。从第一排的第一个点往这一排末端走，到头拐个弯回来，就是U字形的路线。
• 3xN
  考虑3x3，无论如何也无法做到。
• 4xN
  考虑4x3，凹字形路线也是可以的。

观察了这么多，其实可以看出一点规律了。
也就是说如果MN中有一个偶数，就可以符合。
为什么？之前已经知道对于2的情况使用U字形路线，其实那是凹的特例。凹字折返回来要求就是偶数。
考虑大于等于4的偶数情况，假设有N列，N是偶数，然后从左上角出发向下，触底之后折返，到差一行的时候再往右一格再往下。
这个路线下是无视M的值的，因为不影响。
假如MN都是奇数，到最后一列是往下走，回不来。
因此，差不多就能得到结论了：当MN全部为奇数时，返回否。其他情况返回是。
从另一个角度来看，题目要求的路线一定会经过偶数个格子，因此MxN为奇数时不符合。
能不能证明那种路线一定会经过偶数格子？不会证明。

代码

略

总结

面试时要想证明结论的正确性，可能难度比较大，需要数学功底。