50111117海岛帝国：诞辰之日
【试题描述】
YSF自从上次“被盗投降”完（带着一大堆债）回去以后，YSF对“海盗”怀念至今，他想要建立一个“药师傅”海岛帝国。
今天，他要像“管理部”那样去探寻一个新大陆！由于YSF得到了“郭同学”TONY.STARK的赞助。买了好多好多“旧手机”。
从而以某种不法行为GET航拍地图一张！YSF开着热气球，踏(jiu)上(zuo)了(qi)征(le)程(meng)。
YSF跳伞到了一个岛上，由于YSF素有幸运儿之称，所以幸运的他降落在了最大的小岛，但是，YSF一直想了解地图中别的岛，所以请你告诉天(tong)下(xin)闻(wei)名(min)而且还在做梦的YSF，地图上一共有几个小岛，最大的（YSF自己降落的小岛）小岛有多大？（温馨提示：数字表示海拔。0表示海洋，1~9都表示陆地。此处我们把YSF的跳伞点上下左右相连接陆地均视为同一岛屿，海拔不是面积！）
【输入要求】
* 第一行两个整数：n，m，分别表示地图的行和列。
* 接下来的n行m列为地图。
【输出要求】
* 共两行，第一行为小岛的个数N，输出：有N个小岛!
* 第二行为最大的小岛的面积M，输出：YSF降落的小岛面积有M!
【输入实例】
1 10 10 2 1 2 1 0 0 0 0 0 2 3 3 3 0 2 0 1 2 1 0 1 2 4 4 0 1 0 1 2 3 2 0 1 5 3 2 0 0 0 1 2 4 0 0 6 0 0 0 0 0 0 1 5 3 0 7 0 1 2 1 0 1 5 4 3 0 8 0 1 2 3 1 3 6 2 1 0 9 0 0 3 4 8 9 7 5 0 0 10 0 0 0 3 7 8 6 0 1 2 11 0 0 0 0 0 0 0 0 1 0
【输出实例】
有4个小岛!
YSF降落的小岛面积有38!
【其它说明】
地图的大小不超过50*50
【试题分析】
当时刚出过这样的一个乱搞而且把N个方法融合到一起的题，第一反应就是：打dfs+暴力+染色。这当然是最简单粗暴的方法。而且时间复杂度貌似不超啊~~~，所以就乱搞了这样的一个代码，每个点狂搜一遍，然后取最大值就可以求出ans2，但是，ans1怎么求呢？我们知道，目前只搜最大岛的面积函数只要两个参数，分别是x和y，表示YSF的坐标。而我们可以使用染色方法，对于每块走过的陆地染色。实现这个要求可以在我们的DFS函数里加上这样一个参数：color。原来的DFS如下：
1 void dfs(int x,int y) 2 { 3 //定义一个方向数组 4 int next[4][2]={{0,1},//向右走 5 {1,0},//向下走 6 {0,-1},//向左走 7 {-1,0}};//向上走 8 int tx,ty,k; 9 //枚举前进方向 10 for(k=0;k<=3;k++) 11 { 12 //下一步后的坐标 13 tx=x+next[k][0]; 14 ty=y+next[k][1]; 15 if(tx<1 || tx>n || ty<1 || ty>m) continue;//边界判断、 16 //陆地判断 17 if(a[tx][ty]>0 && book[tx][ty]==0) 18 { 19 sum++;//答案+1 20 book[tx][ty]=1;//标记为已走过 21 dfs(tx,ty);//枚举下一个点 22 } 23 } 24 return ; 25 }
改进后的DFS只加了一行，可功能大大提升了
1 void dfs(int x,int y,int color) 2 { 3 //定义一个方向数组 4 int next[4][2]={{0,1},//向右走 5 {1,0},//向下走 6 {0,-1},//向左走 7 {-1,0}};//向上走 8 int tx,ty,k; 9 a[x][y]=color;//对这个格子染色 10 //枚举前进方向 11 for(k=0;k<=3;k++) 12 { 13 //下一步后的坐标 14 tx=x+next[k][0]; 15 ty=y+next[k][1]; 16 if(tx<1 || tx>n || ty<1 || ty>m) continue;//边界判断、 17 //陆地判断 18 if(a[tx][ty]>0 && book[tx][ty]==0) 19 { 20 sum++;//答案+1 21 book[tx][ty]=1;//标记为已走过 22 dfs(tx,ty,color);//枚举下一个点 23 } 24 } 25 return ; 26 }
那么，既然染完色了，拿地图不就变成染色后的了吗？
想一想，有必要担心吗？
DFS1完全不会改变地图，只有DFS2会，我们先求DFS1,再求DFS2。
DFS1只会改变BOOK数组，而即使DFS1会改变地图，拿我们可以直接备份一个地图啊。
所以，可以放心的写代码了~~~
【代码】
1 #include<iostream> 2 using namespace std; 3 int a[50][50]; 4 int book[50][50],n,m,sum,ans=-1,book2[50][50],sum1; 5 void dfs(int x,int y) 6 { 7 int next[4][2]={{0,1}, 8 {1,0}, 9 {0,-1}, 10 {-1,0}}; 11 int tx,ty,k; 12 for(k=0;k<=3;k++) 13 { 14 tx=x+next[k][0]; 15 ty=y+next[k][1]; 16 if(tx<1 || tx>n || ty<1 || ty>m) continue; 17 if(a[tx][ty]>0 && book[tx][ty]==0) 18 { 19 sum++; 20 book[tx][ty]=1; 21 dfs(tx,ty); 22 } 23 } 24 return ; 25 } 26 void dfs2(int x,int y,int color) 27 { 28 int next[4][2]={{0,1}, 29 {1,0}, 30 {0,-1}, 31 {-1,0}}; 32 int tx,ty,k; 33 a[x][y]=color; 34 for(k=0;k<=3;k++) 35 { 36 tx=x+next[k][0]; 37 ty=y+next[k][1]; 38 if(tx<1 || tx>n || ty<1 || ty>m) continue; 39 if(a[tx][ty]>0 && book2[tx][ty]==0) 40 { 41 sum1++; 42 book2[tx][ty]=1; 43 dfs2(tx,ty,color); 44 } 45 } 46 return ; 47 } 48 int main() 49 { 50 int startx,starty,num=0; 51 cin>>n>>m; 52 for(int i=1;i<=n;i++) 53 for(int j=1;j<=m;j++) 54 cin>>a[i][j]; 55 for(startx=1;startx<=n;startx++) 56 for(starty=1;starty<=m;starty++) 57 { 58 book[startx][starty]=1; 59 dfs(startx,starty); 60 book[startx][starty]=0; 61 if(sum>ans) ans=sum; 62 sum=0; 63 } 64 for(int i=1;i<=n;i++) 65 for(int j=1;j<=m;j++) 66 if(a[i][j]>0) 67 { 68 num--; 69 book2[i][j]=1; 70 dfs2(i,j,num); 71 } 72 printf("有%d个小岛!\nYSF降落的小岛面积有%d!\n",-num,ans); 73 }