岛屿数量统计
[问题描述] 在一张地图上，标注有土地和水域两个状态，其中相连接的土地可以连到一起，连到一起的土地可以建造一个岛屿。
[要求] 输入一张地图，输出这张地图上可以有多少个岛屿
[目的] 将实际问题转换成图，将地图中的土地和水看作图中顶点。运用DFS和BFS解决问题。
[ 实现提示 ]
可以用二维数组实现地图，用深度优先和广度优先两种算法实现
遇到的问题：运行代码出不了统计结果，求解决方法（队列要求用自己写的）
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DataType; //便于修改数据类型
//定义队列
typedef struct Queue
{
DataType data;
struct Queue* next;
}QNode;
//设置头尾指针
typedef struct PQueue
{
QNode* head;
QNode* tail;
}PQ;
//初始化队列
void InitQueue(PQ* pq)
{
pq->head=NULL;
pq->tail=NULL;
}
//删除队列
void DeleQueue(PQ* pq)
{
QNode* p=pq->head;
while(p!=NULL)
{
QNode* temp=p->next;
free(p);
p=temp;
}
}
//队列尾部插入
void Push_Queue(PQ* pq,DataType data) //确保队列已经存在
{
assert(pq);
QNode* temp=(QNode*)malloc(sizeof(QNode));
temp->data=data;
if(pq->head==NULL)
{
pq->tail=temp;
pq->head=pq->tail;
}
else
{
pq->tail->next=temp;
pq->tail=temp;
}
}
//队列头部删除
void Pop_Queue(PQ* pq) //确保队列已经存在且不为空
{
assert(pq);
QNode* temp=pq->head->next;
free(pq->head);
pq->head=temp;
}
//判断是否队空
int EmptyQueue(PQ* pq)
{
if(pq->head==NULL)
{
return 1;
}
else
{
return 0;
}
}
//队首
DataType Front_Queue(PQ* pq)
{
int f=EmptyQueue(pq);
if(f)
{
printf("队列为空！！！\n");
exit(-1);
}
return pq->head->data;
}
//队尾
DataType Rear_Queue(PQ* pq)
{
int f=EmptyQueue(pq);
if(f)
{
printf("队列为空！！！\n");
exit(-1);
}
return pq->tail->data;
}
//BFS实现
void BFS(int **str,int row,int col,int x,int y)
{
PQ q;
InitQueue(&q); //初始化
str[row][col]=0; //将当前所在位置置0
int c=row*10+col; //队列中存储一个数字，将两个数字转化为一个存储
Push_Queue(&q,c); //入队
while(!EmptyQueue(&q))
{
c=Front_Queue(&q);
Pop_Queue(&q); //出队
int i=c/10,j=c%10;
if(i>0 && str[i-1][j]==1) //上
{
str[i-1][j]=0;
Push_Queue(&q,(i-1)*10+j);
}
if(i>0 && str[i+1][j]==1) //下
{
str[i+1][j]=0;
Push_Queue(&q,(i+1)*10+j);
}
if(i>0 && str[i][j-1]==1) //左
{
str[i][j-1]=0;
Push_Queue(&q,i*10+j-1);
}
if(i>0 && str[i][j+1]==1) //右
{
str[i][j+1]=0;
Push_Queue(&q,i*10+j+1);
}
}
}
DataType SumIslands1(int **str,int x,int y)
{
if(!str || x==0 || y==0) //判断边界
{
return 0;
}
int i,j,n=0; //n代表统计岛屿的个数
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
{
if(str[i][j]==1) //判断当前是否为1，若是则岛屿数量+1，并将其置0
{
BFS(str,i,j,x,y);
n++;
}
}
}
return n;
}
//DFS实现
void DFS(int **str,int row,int col,int x,int y)
{
str[row][col]=0; //将当前所在位置置0
if(row-1>=0&&str[row-1][col]==1){
DFS(str,row-1,col,x,y);
}
if(row+1<=x-1&&str[row+1][col]==1){
DFS(str,row+1,col,x,y);
}
if(col+1<=y-1&&str[row][col+1]==1){
DFS(str,row,col+1,x,y);
}
if(col-1>=0&&str[row][col-1]==1){
DFS(str,row,col-1,x,y);
}
}
DataType SumIslands2(int **str,int x,int y)
{
int i,j,n=0; //n代表统计岛屿的个数
if(!str || x == 0 || y==0) //判断边界
{
return n;
}
for(i=0;i<x;j++)
{
for(j=0;j<y;j++)
{
if(str[i][j]==1) //判断当前是否为1，若是则岛屿数量+1，并将其置0
{
DFS(str,i,j,x,y);
n++;
}
}
}
return n;
}
int main()
{
int f=1,i,j,x,y;
printf("------------岛屿数量统计系统------------\n");
printf("请输入地图\n");
printf("------------岛屿数量统计系统------------\n");
printf("请分别输入地图大小x,y(空格键开)："); //地图大小，用二维数组实现地图
scanf("%d%d",&x,&y);
DataType map[x][y];
DataType *a[x];
for(i=0;i<x;i++)
{
a[i]=map[i]; //a[i]=&map[i][0]
}
printf("请输入地图相对位置（1表示土地，0表示水域）：");
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
{
scanf("%d",&map[i][j]);
}
}
printf("------------岛屿数量统计系统------------\n");
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
{
printf("%d ",map[i][j]);
}
printf("\n");
}
printf("------------岛屿数量统计系统------------\n");
while(f)
{
printf("------------岛屿数量统计系统------------");
printf("\n1.BFS统计结果；\n2.DFS统计结果。\n");
printf("------------岛屿数量统计系统------------");
printf("\n请输入对应序号（输入0结束运行）：");
int choice; //输入序号进入各功能
scanf("%d",&choice);
switch(choice)
{
case 0:
exit(0);
case 1:
printf("------------岛屿数量统计系统------------\n");
printf("经计算，岛屿的数量：%d\n",SumIslands1(a,x,y));
printf("------------岛屿数量统计系统------------");
break;
case 2:
printf("------------岛屿数量统计系统------------\n");
printf("经计算，岛屿的数量：%d\n",SumIslands2(a,x,y));
printf("------------岛屿数量统计系统------------");
break;
default:
printf("输入错误！！！请重新输入！！！\n");
break;
}
}
return 0;
}
