0
Follow
0
View

# 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

cvbgtasd123 注册会员
2023-02-25 10:13

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

1. 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.
2. 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.
3. In the SumIslands1 function, the variable n that counts the number of islands should have an initial value of 0, not 1.
4. 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* tail;
} PQ;

void InitQueue(PQ* pq) {
pq->tail = NULL;
}
void DeleQueue(PQ* pq) {
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;
pq->tail = temp;
}
else {
pq->tail->next = temp;
pq->tail = temp;
}
}
void Pop_Queue(PQ* pq) {
assert(pq);
}
int EmptyQueue(PQ* pq) {
return 1;
}
else {
return 0;
}
}
DataType Front_Queue(PQ* pq) {
int f = EmptyQueue(pq);
if (f) {
printf("队列为空！！！\n");
exit(-1);
}
}
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;
}

``````

dm2213692 注册会员

Publish Time
2023-02-25 10:13
Update Time
2023-02-25 10:13