用easyx实现flood it 使用dfs 会栈溢出 求解决方法

0
#include <graphics.h> // 引用头文件
#include <conio.h>
#include <time.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>

const int colornum = 6; // 颜色数目

void Change();		// 改变颜色
void Changes();		// 改变矩阵内小方格的颜色;
int arr[9][9];
int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
void dfs(int x, int y, int from, int to);
void display();

void init()
{
	srand(time(NULL));
	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 8; j++)
		{
			arr[i][j] = rand() % 6;
		}
}

void display()
{
	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 8; j++)
		{
			switch (arr[i][j])
			{
				case 0:
					setfillcolor(RED);
					break;
				case 1:
					setfillcolor(BLUE);
					break;
				case 2:
					setfillcolor(GREEN);
					break;
				case 3:
					setfillcolor(YELLOW);
					break;
				case 4:
					setfillcolor(MAGENTA);
					break;
				case 5:
					setfillcolor(BROWN);
					break;
			}
			solidrectangle(i * 35 + 145, j * 35 + 150, (i + 1) * 35 + 145, (j + 1) * 35 + 150);
		}
}

void dfs(int x, int y, int from, int to)
{
	arr[x][y] = to;
	for (int i = 0; i < 4; i++)
	{
		int X = x + dir[i][0];
		int Y = y + dir[i][1];
		if (X >= 0 && X <= 7 && Y >= 0 && Y <= 7)
		{
			if (arr[X][Y] == from)
				dfs(X, Y, from, to);
		}
	}
}

void run()
{
	MOUSEMSG mf; //定义鼠标消息
	int a;
	display();
	while (1)
	{
		int steps = 0;
		mf = GetMouseMsg();
		if (mf.uMsg == WM_LBUTTONUP) //鼠标获取左键点击指令时 
		{
			if (mf.y > 490 && mf.y < 530)
			{
				if (mf.x > 90  && mf.x < 130)	{ a = 0; steps++; }
				if (mf.x > 160 && mf.x < 200)	{ a = 1; steps++; }
				if (mf.x > 230 && mf.x < 270)	{ a = 2; steps++; }
				if (mf.x > 300 && mf.x < 340)	{ a = 3; steps++; }
				if (mf.x > 370 && mf.x < 410)	{ a = 4; steps++; }
				if (mf.x > 440 && mf.x < 480)	{ a = 5; steps++; }
			}
			dfs(0, 0, arr[0][0], a);
			display();
		}
	}
}

int main()
{
	initgraph(800, 600);
	setfillcolor(WHITE);
	solidrectangle(0, 0, 800, 600);
	Change();	// 创建框架
	init();		// 为arr随机赋值
	run();
	getch();
	closegraph();
}

void Change() //选择变换的颜色
{
	for (int i = 0; i < colornum; i++)
	{
		switch (i)
		{
			case 0:
				setfillcolor(RED);
				break;
			case 1:
				setfillcolor(BLUE);
				break;
			case 2:
				setfillcolor(GREEN);
				break;
			case 3:
				setfillcolor(YELLOW);
				break;
			case 4:
				setfillcolor(MAGENTA);
				break;
			case 5:
				setfillcolor(BROWN);
				break;
		}
		solidrectangle(90 + i * 70, 490, 130 + i * 70, 530);
	}
}
ava
光明磊落

2020-3-27

1

看了一下,应该是dfs中的判重语句写错了,自行解决不难

告诫你一下,除非数据量很大,否则dfs是不可能栈溢出的,下次遇到这种情况请先检查你的dfs算法是否出锅

如果数据量真的太大了,请选用基于数组的bfs

另外:慢羊羊村长待会就要来骂你了(逃)

ava
无名氏

2020-3-27

技术讨论社区