dfs 深度优先搜索 四连通块问题

目录

1. 用递归计算四连通块个数

2. 用非递归计算四连通块个数

---

1. 用递归计算四连通块个数

#include 

#define ROW_MAX 100
#define COL_MAX 100		//默认地图的行列

int map[ROW_MAX][COL_MAX];
int ergodic[ROW_MAX][COL_MAX] = { 0 };		//遍历，记录走过的坐标
int g_count = 0;    //统计连通块个数的全局变量
int row, col;	//进行dfs的坐标

void DrawMap(int map[][COL_MAX]);
void Dfs(int x, int y, int map[][COL_MAX]);

void DrawMap(int map[][COL_MAX])
{
	scanf("%d%d", &row, &col);
	int i, j;
	for (i = 0; i < row; i++)
	{
		for (j = 0; j < col; j++)
		{
			scanf("%d", &map[i][j]);
		}
	}
}

void Dfs(int x, int y, int map[][COL_MAX])
{
	if (x < 0 || y < 0 || x == row || y == col)
	{
		return;
	}
	if (ergodic[x][y] == 0)
	{
		ergodic[x][y] = 1;
		g_count++;
	}
	if (map[x][y] == map[x][y + 1] && ergodic[x][y + 1] == 0)
	{
		ergodic[x][y + 1] = 1;
		Dfs(x, y + 1, map);
	}
	if (map[x][y] == map[x][y - 1] && ergodic[x][y - 1] == 0)
	{
		ergodic[x][y - 1] = 1;
		Dfs(x, y - 1, map);
	}
	if (map[x][y] == map[x + 1][y] && ergodic[x + 1][y] == 0)
	{
		ergodic[x + 1][y] = 1;
		Dfs(x + 1, y, map);
	}
	if (map[x][y] == map[x - 1][y] && ergodic[x - 1][y] == 0)
	{
		ergodic[x - 1][y] = 1;
		Dfs(x - 1, y, map);
	}
}

int main()
{
	DrawMap(map);
	int i = 0;
	while (i < row)
	{
		int j = 0;
		while (j < col)
		{
			Dfs(i, j, map);
			j++;
		}
		i++;
	}
	printf("%d\n", g_count);
	return 0;
}

2. 用非递归计算四连通块个数（利用回溯法）

#include 
#include 

#define ROW_MAX 100
#define COL_MAX 100

int g_count = 0;
int map[ROW_MAX][COL_MAX] = { 0 };
int v[ROW_MAX][COL_MAX] = { 0 };

typedef struct LinkedStack
{
	int x;
	int y;
	struct LinkedStack* next;
}Link;

void DrawMap(int map[][COL_MAX], int row, int col)
{
	int i = 0;
	while (i < row)
	{
		int j = 0;
		while (j < col)
		{
			scanf("%d", &map[i][j]);
			j++;
		}
		i++;
	}
}

Link* InitLink(Link* top)
{
	top = (Link*)malloc(sizeof(Link));
	if (!top)
	{
		perror("InitLink::malloc");
		exit(-1);
	}
	top->x = -1;
	top->y = -1;
	top->next = NULL;
	return top;
}

void GetTop(Link* top, int* x, int* y)
{
	Link* p = top->next;
	if (!p)
	{
		printf("LinkedStack is empty\n");
		return;
	}
	*x = p->x;
	*y = p->y;
}

void Push(Link* top, int x, int y)
{
	Link* p = (Link*)malloc(sizeof(Link));
	if (!p)
	{
		perror("Push::malloc");
		exit(-1);
	}
	p->x = x;
	p->y = y;
	p->next = top->next;
	top->next = p;
}

void Pop(Link* top, int* x, int* y)
{
	Link* p = top->next;
	if (!p)
	{
		printf("LinkedStack is empty\n");
		return;
	}
	top->next = p->next;
	*x = p->x;
	*y = p->y;
	free(p);
}

int Empty(Link* top)
{
	if (!top->next)
	{
		return 1;
	}
	return 0;
}

void Destory(Link* top)
{
	Link* p = top->next;
	while (p)
	{
		free(top);
		top = p;
		p = p->next;
	}
}

void Dfs(int map[][COL_MAX], int x, int y)
{
	Link* top = NULL;
	top = InitLink(top);
	if (v[x][y] == 0)
	{
		Push(top, x, y);
		v[x][y] = 1;
		g_count++;
	}
	while (!Empty(top))
	{
		GetTop(top, &x, &y);
		if (map[x][y] == map[x][y + 1] && v[x][y + 1] == 0)
		{
			Push(top, x, y + 1);
			v[x][y + 1] = 1;
			continue;
		}
		else if (map[x][y] == map[x][y - 1] && v[x][y - 1] == 0)
		{
			Push(top, x, y - 1);
			v[x][y - 1] = 1;
			continue;
		}
		else if (map[x][y] == map[x + 1][y] && v[x + 1][y] == 0)
		{
			Push(top, x + 1, y);
			v[x + 1][y] = 1;
			continue;
		}
		else if (map[x][y] == map[x - 1][y] && v[x - 1][y] == 0)
		{
			Push(top, x - 1, y);
			v[x - 1][y] = 1;
			continue;
		}
		else
		{
			Pop(top, &x, &y);
		}
	}
	Destory(top);
}

int main()
{
	int row, col;
	scanf("%d%d", &row, &col);
	DrawMap(map, row, col);
	int i = 0;
	while (i < row)
	{
		int j = 0;
		while (j < col)
		{
			Dfs(map, i, j);
			j++;
		}
		i++;
	}
	printf("%d\n", g_count);
	return 0;
}