DFS and BFS to solve Treasure Island exploration

bfs Treasure Island exploration

Problem description

After figuring out the problem . You will find that it is actually from （6,8） Start breadth first search . Each time, it needs to expand up, down, left and right , When the extended point is greater than 0 Join the queue when , Until the queue is extended . The total number of points added to the queue is the area of the island . Assume that the size of the map does not exceed 50*50.

The code implementation is as follows :

#include <stdio.h>
struct note {
    
	int x;
	int y;

};
int main() {
    
	int i, j, n, m, startx, starty,head,tail,tx,ty,k,sum=1;
	int a[51][51];// Map 
	int book[51][51] = {
    0};// Backup map for marking 
	struct note que[2501];// most 50*50 A little bit 
	int next[4][2] = {
     {
    1,0},{
    0,1},{
    -1,0},{
    0,-1} };// Four directions 
	printf(" Please enter the map with several rows and columns you want to enter ：");
	scanf_s("%d %d", &n, &m);
	printf(" Please enter a map ：\n");
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
			scanf_s("%d", &a[i][j]);
	printf(" Please enter the initial position ：");
	scanf_s("%d %d", &startx, &starty);
	// Initial queue 
	head = 1;
	tail = 1;
	// Assignment initial position 
	que[tail].x = startx;
	que[tail].y = starty;
	// Mark the initial position 
	book[startx][starty] = 1;
	// A party ++
	tail++;
	// When the queue is not empty 
	while (head < tail) {
    
		// Enumerate four directions 
		for (k = 0; k <= 3; k++) {
    
			tx = que[head].x + next[k][0];
			ty = que[head].y + next[k][1];
			// Judge whether you crossed the line 
			if (tx<1 || tx>n || ty<1 || ty>m)
				continue;
			// Joining operation 
			if (a[tx][ty] > 0 && book[tx][ty] == 0) {
    
				book[tx][ty] = 1;// Mark this point 
				sum++;// Increase in area 
				que[tail].x = tx;
				que[tail].y = ty;
				tail++;
			}
		}
		head++;
	}
	printf(" The size of the island is ：%d", sum);
	getchar(); getchar();
	return 0;
}

Input

 Please enter the map with several rows and columns you want to enter ：10 10
 Please enter a map ：
1 2 1 0 0 0 0 0 2 3
3 0 2 0 1 2 1 0 1 2
4 0 1 0 1 2 3 2 0 1
3 2 0 0 0 1 2 4 0 0
0 0 0 0 0 0 1 5 3 0
0 1 2 1 0 1 5 4 3 0
0 1 2 3 1 3 6 2 1 0
0 0 3 4 8 9 7 5 0 0
0 0 0 3 7 8 6 0 1 2
0 0 0 0 0 0 0 0 1 0
 Please enter the initial position ：6 8

Output

 The size of the island is ：38

---

dfs Treasure Island exploration

Problem description

After figuring out the problem . You will find that it is actually from （6,8） Start breadth first search . Each time, it needs to expand up, down, left and right , When the extended point is greater than 0 Join the queue when , Until the queue is extended . The total number of points added to the queue is the area of the island . Assume that the size of the map does not exceed 50*50.

The code implementation is as follows :

#include <stdio.h>
	int book[51][51];
	int a[51][51];
int n, m ,sum=1;
void dfs(int x,int y) {
    
    int next[4][2] = {
     {
    1,0},{
    0,-1},{
    -1,0},{
    0,1} };
    int tx,k, ty;
    for (k = 0; k <= 3; k++) {
    
        tx = x + next[k][0];
        ty = y + next[k][1];
        if (tx<1 || tx>n || ty<1 || ty>m)
            continue;
        if (book[tx][ty] == 0 && a[tx][ty] >= 1) {
    
            book[tx][ty] = 1;
            sum++;
            dfs(tx, ty);

        }
    }
    return;
}
int main() {
    
    int i, j,  startx, starty;
    printf(" Please enter the map with several rows and columns you want to enter ：");
    scanf_s("%d %d", &n, &m);
    printf(" Please enter a map ：\n");
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            scanf_s("%d", &a[i][j]);
    printf(" Please enter your starting position ：");
    scanf_s("%d %d", &startx, &starty);
    book[startx][starty] = 1;
    dfs(startx, starty);
    printf(" The area of the island is ：%d", sum);
    getchar(); getchar();
    return 0;

}

Input

 Please enter the map with several rows and columns you want to enter ：10 10
 Please enter a map ：
1 2 1 0 0 0 0 0 2 3
3 0 2 0 1 2 1 0 1 2
4 0 1 0 1 2 3 2 0 1
3 2 0 0 0 1 2 4 0 0
0 0 0 0 0 0 1 5 3 0
0 1 2 1 0 1 5 4 3 0
0 1 2 3 1 3 6 2 1 0
0 0 3 4 8 9 7 5 0 0
0 0 0 3 7 8 6 0 1 2
0 0 0 0 0 0 0 0 1 0
 Please enter the initial position ：6 8

Output

 The area of the island is ：38

---

The number of small islands

Problem description

Code implementation

#include <stdio.h>
	int book[51][51];
	int a[51][51];
	int n, m, sum = 1 , num;
void dfs(int x, int y,int num) {
    
	int next[4][2] = {
     {
    1,0},{
    0,-1},{
    -1,0},{
    0,1} };
	int tx, k, ty;
	
	for (k = 0; k <= 3; k++) {
    
		tx = x + next[k][0];
		ty = y + next[k][1];
		
		if (tx<1 || tx>n || ty<1 || ty>m)
			continue;
		if (book[tx][ty] == 0 && a[tx][ty] >= 1) {
    
			book[tx][ty] = 1;
			a[tx][ty] = num;
			//sum++;
			dfs(tx, ty,num);

		}
	}
	return;
}
int main() {
    
	int i, j, startx, starty;
	printf(" Please enter the map with several rows and columns you want to enter ：");
	scanf_s("%d %d", &n, &m);
	printf(" Please enter a map ：\n");
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
			scanf_s("%d", &a[i][j]);
	
	
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++) {
    
			if (a[i][j] > 0) {
    
				num--;
				a[i][j] = num;
				dfs(i, j, num);
			}
		}
	printf(" The dyed island map is ：\n");
	for (i = 1; i <= n; i++) {
    
		for (j = 1; j <= m; j++) {
    
			printf("%3d", a[i][j]);
				
				
			
		}
		printf("\n");
	}
		
	
	printf(" The number of islands is ：%d", -num);
	getchar(); getchar();
	return 0;

}

Input

 Please enter the map with several rows and columns you want to enter ：10 10
 Please enter a map ：
1 2 1 0 0 0 0 0 2 3
3 0 2 0 1 2 1 0 1 2
4 0 1 0 1 2 3 2 0 1
3 2 0 0 0 1 2 4 0 0
0 0 0 0 0 0 1 5 3 0
0 1 2 1 0 1 5 4 3 0
0 1 2 3 1 3 6 2 1 0
0 0 3 4 8 9 7 5 0 0
0 0 0 3 7 8 6 0 1 2
0 0 0 0 0 0 0 0 1 0

Output

 The dyed island map is ：
 -1 -1 -1  0  0  0  0  0 -2 -2
 -1  0 -1  0 -3 -3 -3  0 -2 -2
 -1  0 -1  0 -3 -3 -3 -3  0 -2
 -1 -1  0  0  0 -3 -3 -3  0  0
  0  0  0  0  0  0 -3 -3 -3  0
  0 -3 -3 -3  0 -3 -3 -3 -3  0
  0 -3 -3 -3 -3 -3 -3 -3 -3  0
  0  0 -3 -3 -3 -3 -3 -3  0  0
  0  0  0 -3 -3 -3 -3  0 -4 -4
  0  0  0  0  0  0  0  0 -4  0
 The number of islands is ：4

summary