农夫约翰带着奶牛去海边度假了!奶牛生活在N个(1<=N<=15)岛屿上,这些岛屿位于R x C网格(1<=R,C<=50)上。岛是网格上标记为“X”的最大连通正方形组,如果两个“X”共享一条边,则它们是连通的。(因此,共享一个角的两个“X”不一定是连接的。)
然而,贝茜来晚了,所以她要和FJ一起乘直升机进来。因此,她可以首先降落在她选择的任何岛屿上。她想至少参观一次所有的奶牛,所以她将在岛屿之间旅行,直到她至少参观了所有N个岛屿一次。
有’S’,’X’,’.’三种地形,所有判定相邻与行走都是四连通的。我们设’X’为陆地,一个’X’连通块为一个岛屿,’S’为浅水,’.’为深水。刚开始你可以降落在任一一块陆地上,在陆地上可以行走,在浅水里可以游泳。并且陆地和浅水之间可以相互通行。但无论如何都不能走到深水。你现在要求通过行走和游泳使得你把所有的岛屿都经过一边。Q:你最少要经过几格子浅水区?保证有解。