数据结构（c++）--宝岛探险

yan一个小岛由一个主岛和一些复附属岛屿组成，该岛使用一个二维矩阵表示，其中数字表示海拔，0表示海洋，1~9表示陆地。探险家乘坐飞机降落在（6,8）处，现在需要统计探险家降落的小岛的面积大小，我们将探险家降落点上下左右相连接的陆地视作同一个岛屿

BFS

完整代码：

#include
using namespace std;
struct note {
	int x;
	int y;
};
int a[11][11];
int main() {
	struct note que[401];
	int next[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };//右下左上
	int i,j, startx , starty ,n,m,tx,ty,k,sum=0;
	//数据初始化
	int tail = 1, head = 1;
	int book[11][11] = { 0 };
	
	//输入行列，起点，再输入矩阵数据
	cin >> n >> m >> startx >> starty;
	book[startx][starty] = 1;
	//队列初始化
	que[tail].x = startx;
	que[tail].y = starty;
	tail++;
	for (i = 1;i <= 10;i++)
		for (j = 1;j <= 10;j++)
			cin >> a[i][j];
	//当队列不为空的时候循环
	while (head < tail) {
		for (k = 0;k <= 3;k++) {
			tx = que[head].x + next[k][0];
			ty = que[head].y + next[k][1];
			if (tx<0 || tx>n - 1 || ty<0 || ty>n - 1)
				continue;
			if (a[tx][ty] != 0 && book[tx][ty] == 0) {
				book[tx][ty] = 1;
				que[tail].x = tx;
				que[tail].y = ty;
				tail++;
				sum++;
			}
		}
		head++;
	}
	cout << sum+1;
	return 0;
}

DFS

#include
using namespace std;
int a[11][11], book[11][11];
int p, q,n,m, sum = 1;
void dfs(int x, int y) {
	int k, next[4][2] = { {0,1},{1,0},{-1,0},{0,-1} };
	int tx, 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 (a[tx][ty] != 0 && book[tx][ty] == 0) {
			book[tx][ty] = 1;
			sum++;
			dfs(tx, ty);
		}
	}
	return;
}
int main() {
	int startx, starty,i,j;
	cin >> n >> m;
	cin >> startx >> starty;
	
	p = startx;q = starty;
	book[startx][starty] = 1;
	for (i = 1;i <= n;i++)
		for (j = 1;j <= m;j++)
			cin >> a[i][j];
	dfs(startx, starty);
	cout << sum;
	return 0;
}

 样例输入：

10 10 6 8
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

样例输出：

38

进阶版：怎样知道有多少个独立的小岛？

#include
using namespace std;
int a[11][11], book[11][11];
int n,m, sum = 1;
void dfs(int x, int y,int color) {
	int k, next[4][2] = { {0,1},{1,0},{-1,0},{0,-1} };
	int tx, ty;
	a[x][y] = color;
	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 (a[tx][ty] != 0 && book[tx][ty] == 0) {
			book[tx][ty] = 1;
			sum++;
			dfs(tx, ty,color);
		}
	}
	return;
}
int main() {
	int i,j,num=0;
	cin >> n >> m;
	for (i = 1;i <= n;i++)
		for (j = 1;j <= m;j++)
			cin >> a[i][j];

	for(i=1;i<=n;i++)
		for (j = 1;j <= n;j++) {
			if (a[i][j] > 0) {
				num--;
				book[i][j] = 1;
				dfs(i, j, num);
			}
			
		}
	for (i = 1;i <= n;i++){
		for (j = 1;j <= m;j++)
			cout << a[i][j] << " ";
	cout << endl;
}
	cout << -num;
	return 0;
}