海岛淹没（DFS）

海岛淹没（DFS）"/>

海岛淹没（DFS）

你有一张某海域NxN像素的照片，”.”表示海洋、”#”表示陆地，如下所示：
…….
.##….
.##….
….##.
…####.
…###.
…….
其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
…….
…….
…….
…….
….#…
…….
…….
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
【输出格式】
一个整数表示答案。
【输入样例】
7
…….
.##….
.##….
….##.
…####.
…###.
…….
【输出样例】
1
【输入样例】
10
…
.###…###.
.###…###.
.########.
…
.###…#…
.#.#…#…
.###…
…
…
【输出样例】
2
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms

运用DFS先求出原先的海岛数量sum1，然后找出四周都有#的#的岛屿，求出其数量sum2。
用原始岛屿数减去得到sum=sum1-sum2。
具体代码如下：

#include<stdio.h>
#include<iostream>
using namespace std;
#include<algorithm>
//这个思路就是求哪个岛屿有四周都是#的#，然后剩下的岛屿就是被淹没的数量（完全被浸染的数量） 
char map[101][101];
char map1[101][101];
int move[4][2]={-1,0,1,0,0,1,0,-1};
int ans[110]={0};
int vis[101][101]={0};  //未被访问标记为0 void DFS(int x,int y,int n)   //求总的岛屿数 
{int next_x,next_y;vis[x][y]=1;  //表示被访问过 for(int i=0;i<4;i++){next_x=x+move[i][0];next_y=y+move[i][1];if(next_x>=0&&next_x<n&&next_y>=0&&next_y<n&&vis[next_x][next_y]==0)   //在范围内{if(map[next_x][next_y]=='#'){DFS(next_x,next_y,n);}   } }
}int main()
{int n;scanf("%d",&n)；for(int i=0;i<n;i++){getchar();for(int j=0;j<n;j++){scanf("%c",&map[i][j])；} }int sum1=0,sum2=0;//sum1代表淹没前岛屿数量，sum2代表淹没的岛屿数量 int len=0;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(map[i][j]=='#'&&vis[i][j]==0) //如果是‘#’且没被访问过 {DFS(i,j,n);sum1++; }} }for(int i=1;i<n-1;i++){for(int j=1;j<n-1;j++){if(map[i-1][j]=='#'&&map[i+1][j]=='#'&&map[i][j-1]=='#'&&map[i][j+1]=='#')ans[len]++;} }for(int i=0;i<sum1;i++){if(ans[i]==0)sum2++;}printf("%d %d ",sum1,sum2);int sum=sum1-sum2;printf("%d",sum);return 0;} 

接下来还会补充几个DFS的题，大体轮廓相似，但每个题又有不同之处。
一、剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

答案：116

int sum=0;#include<stdio.h>
#include<algorithm>
int map[12]={1,2,3,4,6,7,8,9,11,12,13,14};
int aa[5]; //保存五个数 
int vis[5]={0}; //标记 
int move[4]={-1,1,-5,5};  //上下左右四个方向 
/*  1  2  3  46  7  8  911 12 13 14
*/
//因为4+1 9+1不能连上 
int count=0;
void DFS(int n)
{for(int i=0;i<4;i++) {int t=aa[n]+move[i]; if(t<1||t>14||t==5||t==10) continue;for(int j=0;j<5;j++){if(!vis[j]&&aa[j]==t){vis[j]=1;DFS(j);}}}
} 
int main()
{for(int i=0;i<12;i++)   //因为是五个数所以五重循环 {for(int j=i+1;j<12;j++){for(int k=j+1;k<12;k++){for(int m=k+1;m<12;m++){for(int n=m+1;n<12;n++){aa[0]=map[i];aa[1]=map[j];aa[2]=map[k];aa[3]=map[m];aa[4]=map[n];for(int i=0;i<5;i++)//每找到五个数就要全部初始化为0，仅在刚开始初始化是不够的 vis[i]=0; vis[0]=1;DFS(0);int flag=1;for(int i=0;i<5;i++){if(vis[i]!=1){flag=0;break;}}if(flag==0)  continue;elsecount++;   }} } }}printf("%d",count);return 0;} 

标题：方格分割
6x6的方格，沿着格子的边线剪开成两部分。要求这两部分的形状完全相同。如图：p1.png, p2.png, p3.png 就是可行的分割法。试计算：包括这3种分法在内，一共有多少种不同的分割方法。注意：旋转对称的属于同一种分割法。请提交该整数，不要填写任何多余的内容或说明文字。

代码如下：

//方格分割（分成完全一样的两部分）问有多少中分法
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int str[8][8];
int move[4][2]={{0,1},{0,-1},{-1,0},{1,0}};//上下左右四个方向 
int sum=0;
int vis[8][8]={0};
void DFS(int r,int c) //以（r,c）为起点开始回溯
{if(r==0||c==0||r==6||c==6){sum++;return;}for(int i=0;i<4;i++){int next_x=r+move[i][0];int next_y=c+move[i][1];if(!vis[next_x][next_y]){vis[next_x][next_y]=1;vis[6-next_x][6-next_y]=1;DFS(next_x,next_y);vis[next_x][next_y]=0;vis[6-next_x][6-next_y]=0; }}  
}
int main()
{vis[3][3]=1;DFS(3,3);printf("%d",sum/4);return 0;}