本题是一道非常经典的并查集题目。
首先我们来分析一下，每周新添加的陆地会对岛屿数目有什么影响。
我们用X表示新添加的陆地，X上下左右四个位置分别用1234来表示：
.1.
3X4
.2.
1) X周围没有岛屿：
...
.X.
...
这时新添加的X会导致岛屿数目+1
2) X周围有一座岛屿：
.#. .##
.X. .X# (1和4属于同一座岛屿)
... ...
这时新添加的X会与#的岛屿合并，岛屿数目不变
3) 同理，如果X周围有二、三、四座岛屿，那么新添加的X会把这些岛屿都合并成一座岛屿。岛屿数目-1, -2, -3。
.#.
#X#
.#.
通过上面的分析，我们发现解决这道题目需要一种数据结构或算法可以用比较低的复杂度快速实现：
1) 查询一块陆地属于哪个岛屿
2) 合并两个岛屿
如果我们把一块陆地看作一个元素，一个岛屿看作一个集合。那么并查集就是解决以上两个问题的利器。
关于并查集可以参考#1066题或者网上的资料，这里不再赘述。
using namespace std;
char arc[maxn][maxn]; int pre[maxn*maxn]; int mlen,nlen;
int find(int v) { if(pre[v]==v) return v; else{ pre[v]=find(pre[v]); return pre[v]; } }
void merge(int v,int u) { int t1=find(v),t2=find(u); if(t1!=t2) if(t1
void merge_4_dir(int x,int y) { int tt=x*nlen+y; int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; for(int i=0; i<4; i++){ int tx=x+dx[i]; int ty=y+dy[i]; int uu=tx*nlen+ty; if(tx>=0&&tx=0&&ty
int main() { //输入地图的高和长 while(cin>>mlen>>nlen) { for(int i=0;i>arc[i]; int cx,cy; for(int x=0;x
并查集，很高效的解决“标记-合并”问题