interview--- 警察抓逃犯问题

题目：A国由1000000个岛组成，岛与岛之间只能用船作为交通工具，有些岛之间有船来往，从任意一个岛都可以去到另外任一个岛，当然其中可能要换船。现在有一个警 察要追捕一个逃犯，开始时他们在不同的岛上，警察和逃犯都是每天最多乘一次船，但这个逃犯还有点迷信，每个月的13日不乘船，警察则不迷信。警察每天乘船前都知 道逃犯昨天在哪个岛上，但不知道他今天会去哪个岛。请证明，警察一定可以抓到逃犯(即到达同一个岛)。

解答：

初始的时候警察和罪犯在两个岛上，这两个岛一定是连通的，它们之间的最短路经为n。那么警察在n天之后可以到达逃犯初始的岛上。然后沿着逃犯走过的路线 
前进，于是每月13号时警察和逃犯之间的距离减少1，在最多n月之后可以追上逃犯。