Question about #c language # : Output how many islands can be on this map [objective] To transform the actual problem into a graph, and regard the land and water in the map as the vertex of the graph

#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; }

the reference answer GPT ᴼ ᴾ ᴱ ᴺ ᴬ ᴵ < br / > the code there is a mistake:

In the BFS function, i> is written in the judgment of up, down, left and right directions; 0, this should be changed to i> =0 to access the top and leftmost positions correctly.
In the DFS function, in the up, down, left and right direction of the judgment, check the up and left direction of the code is written backwards.
In the SumIslands1 function, the variable n that counts the number of islands should have an initial value of 0, not 1.
Before calling the BFS function or DFS function, you should first check whether the value of the current position is 1. If it is 0, no BFS or DFS is needed.

The modified code is as follows:

#include
#include
#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;
}

void BFS(int **str, int row, int col, int x, int y) {
    PQ q;
    InitQueue(&q);
    str[row][col] = 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 >= 1 && str[i - 1][j] == 1) {
            str[i - 1][j] = 0;
            Push_Queue(&q, (i - 1) * 10 + j);
        }
        if (i < x - 1//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)
{
if(!str || x==0 || y==0) //判断边界
{
return 0;
}
int i,j,n=0; //n代表统计岛屿的个数
for(i=0;ifor(j=0;jif(str[i][j]==1) //判断当前是否为1，若是则岛屿数量+1，并将其置0
{
DFS(str,i,j,x,y);
n++;
}
}
}
return n;
}

int main()
{
int i,j,x,y;
DataType p=NULL;
printf("输入地图的行数和列数：");
scanf("%d%d",&x,&y);
p=(DataType)malloc(sizeof(DataType*)x);
for(i=0;i[i]=(DataType)malloc(sizeof(DataType)*y);
}
printf("请输入地图：\n");
for(i=0;ifor(j=0;j"%d",&p[i][j]);
}
}
printf("使用BFS算法计算岛屿的数量为：%d\n",SumIslands1(p,x,y));
printf("使用DFS算法计算岛屿的数量为：%d\n",SumIslands2(p,x,y));
for(i=0;i[i]);
}
free(p);
return 0;
}

Question about #c language # : Output how many islands can be on this map [objective] To transform the actual problem into a graph, and regard the land and water in the map as the vertex of the graph

Question about #c language # : Output how many islands can be on this map [objective] To transform the actual problem into a graph, and regard the land and water in the map as the vertex of the graph

0 Comment

0 Comment

About the Author

Question Info

Related Question

c++: std::atomic_flag::test_and_set中的std::memory_order只通过一组线程执行一次某些工作

Xamarin形成android -谷歌地图应用程序未找到

HashMap问题:填充后缺少条目

Android应用程序不会从登录或注册活动进入下一个活动

映射QWidget中心位置到QGraphicsScene坐标?

grafana prometheus不区分大小写查询

无法使用Openj9 JVM运行Cassandra

在apk版本中，原生Android gmail和firebase手机otp登录不工作

共享偏好,复选框,Kotlin, Android

带有变量字段名的GraphQL类型