Readme

1568.Minimum-Number-of-Days-to-Disconnect-Island

此题乍看没有头绪。但是考虑到这只是一个6分题，必然有巧解。

首先想到的是，如果一个格子最多只会被四个邻接陆地包围，所以答案不会超过4.

其次，想到肯定不会所有的格子都被四个邻接陆地包围，肯定会有“边缘”的格子，有一边是邻接水域或者边界。对于这个格子，我们只要断开另外三面陆地连接即可。所以答案不会超过3.

再看一下例子，发现sample里的答案没有超过2的。细想一下，确实无论什么几何形状，都会有“角落”的格子。所谓的“角落”，指的是只有两个邻接点是与大陆相连。所以答案又可以缩小为不会超过2.

如今答案的可能只有0，1，2。答案是否为零很好判断，扫一遍全局看是否已经存在多于一个岛，或者压根没有岛。

答案是否为1呢？这意味着只要删除一块陆地，就能使得岛的数量大于等于2，或者没有任何岛。于是我们可以遍历每一块陆地，假设删除它，再查看一下剩下的地形的岛的数量即可。遍历一块“删除之地”大概是o(900)，然后每次搜索全局数一下剩余岛的个数也是o(900)，总共的时间复杂度是o(810000)，是可以接受的。如果答案不为1，那么答案就肯定是2了。

所以本题的本质就是一个暴力枚举+BFS搜索判断岛数量。