分类：C

LeetCode-338. Counting Bits

2016年4月6日 by Lnyan·0评论

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

Follow up:

It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

Hint:

You should make use of what you have produced already.
Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
Or does the odd/even status of the number help you in calculating the number of 1s?

一开始没看 Hint ，看到题目的要求下意识的想到了树状数组中 lowbit 的用法，但是感觉这样还是不能满足 O(N) 的时间要求……

思路大体是这样的，首先从 num 开始计算出 1 的个数，然后通过形似 num-=(num&-num) 的运算消去最后一个 1 ，完成对下一个 num 的计数，然后依次类推。之后从 num 递减，若出现了未记录的数，则继续如上的计算。

代码如下：

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* countBits(int num, int* returnSize) {
    int *result,i,j,temp=0;
    *returnSize=num+1;
    result=(int *)malloc(*returnSize*sizeof(int));
    for(i=0;i<*returnSize;i++)
    {
    	result[i]=0;
    }
    for(i=num;i>=0;i--)
    {
    	if(result[i]!=0)
    	{
    		continue;
    	}
    	else
    	{
    		temp=i;
    		for(j=0;j<8*sizeof(int);j++)
    		{
    			if(temp&1)
    			{
    				result[i]++;
    			}
    			temp=temp>>1;
    		}
    		temp=i;
    		j=0;
    		while(temp!=0)
    		{
    			if(temp&1)
    			{
    				j++;
    			}
    			temp=temp>>1;
    			result[temp]=result[i]-j;
    		}
    		temp=i;
    		j=1;
    		while(temp!=0)
    		{
    			temp-=(temp&-temp);
    			result[temp]=result[i]-j;
    			j++;
    		}
    	}
    }
    return result;
}

/**

* Return an array of size *returnSize.

* Note: The returned array must be malloced, assume caller calls free().

int* countBits(int num, int* returnSize) {

int *result,i,j,temp=0;

*returnSize=num+1;

result=(int *)malloc(*returnSize*sizeof(int));

for(i=0;i<*returnSize;i++)

{

result[i]=0;

}

for(i=num;i>=0;i--)

{

if(result[i]!=0)

{

continue;

}

else

{

temp=i;

for(j=0;j<8*sizeof(int);j++)

{

if(temp&1)

{

result[i]++;

}

temp=temp>>1;

}

temp=i;

j=0;

while(temp!=0)

{

if(temp&1)

{

j++;

}

temp=temp>>1;

result[temp]=result[i]-j;

}

temp=i;

j=1;

while(temp!=0)

{

temp-=(temp&-temp);

result[temp]=result[i]-j;

j++;

}

return result;

}

背景

2015 年 C 程序设计专题课程第三次 Project，基于 bhh 老师移植加改写的 watcom c + graphics.h 实现。

除了 dosbox 效率比较坑，也没有什么太多的问题吧（其实是已经记不清了

v20150614 版俄罗斯方块（其实只是修改日期……）实现了基本的功能 + 排行榜，但是具体的设置界面当时为了赶 DDL 就没有去写，时间都基本耗在 bgm 的实现上去了……（找了各种 dos 下 wav 的播放实现，翻遍了各种“远古”的论坛，最后却发现库函数里提供了相应的函数 T_T

v20150628 版是为了课上展示准备的版本，当时用了一上午？把界面改的舒服了一些，同时增加了方块在底部的投影以及方块的暂存功能。

打字游戏

俄罗斯方块v20150614

俄罗斯方块v20150628

报告及源码

一、问题说明

在Dosbox环境下，自行设计相关的算法与数据结构，实现图形化的俄罗斯方块与文本形式的打字游戏。

二、算法设计与说明

俄罗斯方块的算法主要涉及到对应图形的绘制以及对应储存矩阵（数组）的操作。我们采用了通过显示器频率中断控制扫描状态池矩阵的数据进行全屏输出与脏矩形绘制相结合的方法进行了图形的绘制，然而由于平台的限制，画面仍有一定可能出现抖动或卡滞的情况。在对方块的操作中，我们则每次获取按键后，扫描矩阵以获得当前活动的方块区域，在对其进行对应的移位或伪转置操作（实现旋转）。（By LLonely）

打字游戏的设计则是随机获取单词，并依次在随机位置输出，判断按键与屏幕上活动单词的匹配情况，再依次循环判断，若不匹配，则重置标记，再次重新开始匹配。如果有活动单词被匹配完毕，则激活动画，并清除该单词。通过循环与延迟函数更新屏幕的状态，控制活动单词的产生、移动与消失，同时刷新得分与统计数据。（By MagicPants）

三、数据结构设计与说明

在俄罗斯方块中：

采用了一个状态池（pool结构的二维数组）来储存所有池内位置的状态与颜色，也就是此前所提到的矩阵。结构定义如下：

C

struct pool { int state; int color; }tetris[FIX_Y+20][10];//FIX_Y=4为不可见区域

1
2
3
4
5

struct pool
{
int state;
int color;
}tetris[FIX_Y+20][10];//FIX_Y=4为不可见区域

采用了一个brick_default结构来储存不同种类方块（I、O、L、J、S、Z、T形方块）的颜色、规模与形状。结构定义如下：

C#

struct brick_default { long color; int scale; int pattern[4][4]; }brick[7];

1
2
3
4
5
6

struct brick_default
{
long color;
int scale;
int pattern[4][4];
}brick[7];

采用SCORE结构储存得分与对应信息。结构定义如下：

C

typedef struct { unsigned long score; time_t _time; int total; } SCORE;

1
2
3
4
5
6

typedef struct
{
unsigned long score;
time_t _time;
int total;
} SCORE;

采用了一个menu_entry结构进行菜单的储存，同时开发了framework模块对该结构进行操作（未完成）。结构定义如下：

struct menu_entry
{
	char name[51];
	int is_active;
	int is_available;
	struct menu_entry *previous;
	struct menu_entry *next;
	int is_with_radio;
	radio * option;
};

struct menu_entry

{

char name[51];

int is_active;

int is_available;

struct menu_entry *previous;

struct menu_entry *next;

int is_with_radio;

radio * option;

};

采用了一个position结构的一维数组来储存变更的状态以实现脏矩形绘制。

在打字游戏中：

采用了白老师所提供示例中的一系列针对字典操作的数据结构。
定义了一个WORD结构来储存对应的单词。结构定义如下

C

typedef struct { char word[20]; int x,y,flag,is_null; }WORD;

1
2
3
4
5

typedef struct
{
char word[20];
int x,y,flag,is_null;
}WORD;

四、系统设计难点与解决方案

打字游戏除字典读取外无难点（有示例可解决）。以下难点针对于俄罗斯方块。

1、难点：

①俄罗斯方块的旋转操作。

②绘图效果的优化。

③动态效果与时间控制。

2、解决方案（与难点对应）：

①确定当前活动方块的范围后，截取该区域的活动方块状态，进行矩阵的旋转操作，适当调整形状后，与状态池进行比对，判断能否放入状态池，若能则在状态池中清除原有的活动方块，更新为新的活动方块；若不能则放弃此次旋转。

②采用脏矩形的方法绘制，明显降低了画面的抖动。

③采用通过读取屏幕的垂直回扫中断进行时间的控制。

五、人员分工说明

本小组依旧采用Git进行版本库控制。其中，俄罗斯方块主要由LLonely开发，MagicPants负责测试及细节的调整，打字游戏主要由MagicPants开发，LLonely负责测试以及对应的优化。

六、源码

我会在 GitHub 上建一个 Repo ，把那些代码 push 上去……（不过肯定不是原 Repo

背景

大一下学期 C 程序设计专题（C大程）的第二个专题，关于链表的操作，比较水的一次 Project ，当时正好生病了，便也没做的太认真，一开始是打算采用 GUI 或者 TeX 或者 HTML + CSS 实现多项式的显示的，以及幂为多项式的运算的，然而最后 DDL 在五一期间，赶完通识课的论文后就没有精力了（尤其是还生病了），当时的坑就放弃了。将具体链表操作的实现（毕竟比较简单）交给了队友 MagicPants ，然后我就实现了简单的 IO 操作和文件的模块化划分（这次变成我是可有可无的角色了(⊙﹏⊙)）。不过当时正好看了《 C 专家编程》，便尝试了一下可变参量列表。

报告及源码

继续阅读

2015-03-迷宫寻径-Maze-Project

2016年3月1日 by Lnyan·0评论

效果图

Console 版

GUI 版（EGE实现）

感想

怎么说呢，在当时，对我而言，这也算是有一定的难度的。当时最为繁琐的就是图形库的选择与图形化的实现，尤其是图形库的选择过程。当时尝试了GTK+, SDL, easyX, EGE，最后只有 easyX 和 EGE 能在我的电脑上正常的使用。然后又听说 EGE 的效率比 easyX 高，于是便选择了 EGE ，看了大约两个小时文档（然后发现几乎都没用到），最后写出了 GUI 版的 Project。

然后为了演示的效果，又用深度优先搜索实现了迷宫的自动生成。最终与基于递归实现的迷宫寻径整合到一起，实现了这个 Project。

具体实现及思路

采用一个全局的动态二维数组用于储存迷宫信息（如下表所示），同时记录墙体与空间位置。然后用若干个结构体记录坐标。

墙	起	墙	墙	墙
墙	空	墙	空	终
墙	空	墙	空	墙
墙	空	空	空	墙
墙	墙	墙	墙	墙

迷宫生成的方式，则是参考了 Wikipedia 的描述，首先将原始迷宫初始化为一张完全方格图，然后设定起点和终点，从起点开始进行深度优先搜索，每次遍历的方向与步数都随机取值，途中遇能拆的墙（墙对面有未遍历过的空间）则“拆墙”（将该位置改为空余的空间），直至遍历全图。

至于路经的寻找则是用相对简单的递归实现的（实际也是一个深度优先搜索，其实用广度优先搜索效率会高一些？，但是题目要求使用递归实现），一个简简单单的回溯过程。将终点位置作为递归出口，递推关系为相邻两空余点间的水平或垂直移动——若可以从当前坐标移动到某一相邻坐标（墙壁或路径点或标记不可通点为无法移动到的点），则将该点标记为路径点，从可移动位置进行下一轮的移动；若从当前点无法移动到其所有相邻的坐标，则将改点标记为不可通点，从当前函数返回，继续进行上一路径点所对应的移动过程。以此类推，在迷宫可通、迷宫大小合适的情况下，必然可得出至少一个可行解。（这一段是当时在报告上写的，直接了粘贴过来）这种思路很简单，可惜递归的实现一点都不优雅，当问题规模增大时，必然会堆栈溢出。尽管当时我的能力足以实现一个模拟堆栈的版本，但精力有限（总不能将时间都耗在这门课上），未去实现。

（差不多都忘了……早知当时就该顺手更新上来的）

源码

有点惨不忍睹……算是自己的黑历史吧。。。

当时交的版本随机遍历以生成迷宫，未采用 DFS

（当时写的修改版中函数竟然用的是 ‘dps’ 什么鬼(⊙﹏⊙)）

Console 版（上交时的格式）

/* Name: Maze-In-Console
 * ############################################
 * Author: LLonely
 * ID: xxx（删掉了）
 * Email: i#llonely.com
 * Website: llonely.com
 * --------------------------------------------
 * Maze-Core & Maze-Console-Dynamic-Expression & Maze-Random-Generator
 */
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<windows.h>
#define WALL -1
#define START -3
#define END -4
#define NOTWAY -2
#define MX 39
#define MY 149
#define _Y (MY*2+1)
#define _X (MX*2+1)
#define PERR(bSuccess, api){if(!(bSuccess)) printf("%s:Error %d from %s \
on line %d\n", __FILE__, GetLastError(), api, __LINE__);}
// int maze[MY*2+1][MX*2+1],sign=1,_x=0,_y=0;
int **maze,sign=1,_x=0,_y=0;
unsigned long speed=50;
struct position
{
	int x;
	int y;
}direction[]={{1,0},{-1,0},{0,1},{0,-1}},maker,temp,explorer;

void gotoxy(int x, int y)
{
	CONSOLE_SCREEN_BUFFER_INFO    csbiInfo;
	HANDLE    hConsoleOut;
	hConsoleOut = GetStdHandle(STD_OUTPUT_HANDLE);
	GetConsoleScreenBufferInfo(hConsoleOut, &csbiInfo);
	csbiInfo.dwCursorPosition.X = x;
	csbiInfo.dwCursorPosition.Y = y;
	SetConsoleCursorPosition(hConsoleOut, csbiInfo.dwCursorPosition);
}

void cls(HANDLE hConsole)
{
	COORD coordScreen = { 0, 0 }; 
	BOOL bSuccess;
	DWORD cCharsWritten;
	CONSOLE_SCREEN_BUFFER_INFO csbi;
	DWORD dwConSize;
	bSuccess = GetConsoleScreenBufferInfo( hConsole, &csbi );
	PERR( bSuccess, "GetConsoleScreenBufferInfo" );
	dwConSize = csbi.dwSize.X * csbi.dwSize.Y;
	bSuccess = FillConsoleOutputCharacter( hConsole, (TCHAR) ' ',
	dwConSize, coordScreen, &cCharsWritten );
	PERR( bSuccess, "FillConsoleOutputCharacter" );
	bSuccess = GetConsoleScreenBufferInfo( hConsole, &csbi );
	PERR( bSuccess, "ConsoleScreenBufferInfo" );
	bSuccess = FillConsoleOutputAttribute( hConsole, csbi.wAttributes,
	dwConSize, coordScreen, &cCharsWritten );
	PERR( bSuccess, "FillConsoleOutputAttribute" );
	bSuccess = SetConsoleCursorPosition( hConsole, coordScreen );
	PERR( bSuccess, "SetConsoleCursorPosition" );
	return;
}

int can_move(int y,int x)
{
	if(y<0||x<0||x>=_x||y>=_y)
		return 0;
	else if(maze[y][x]==WALL||maze[y][x]==NOTWAY||maze[y][x]==START||maze[y][x]>0)
		return 0;
	else
		return 1;
}

void print_solution(void)
{
	int i,j,max=0;
	HANDLE    hConsoleOut;
	hConsoleOut = GetStdHandle(STD_OUTPUT_HANDLE);
/*	struct step
	{
		int y;
		int x;
	}steps[_X*_Y+1],end;*/
	struct step
	{
		int y;
		int x;
	}*steps,end;
	steps=(struct step*)calloc(_y*_x+1,sizeof(struct step));
	for(i=0;i<_y;i++)
	{
		for(j=0;j<_x;j++)
		{
			if(maze[i][j]==WALL)
				printf("%c",'#');
			else if(maze[i][j]>0)
			{
				steps[maze[i][j]].y=i;
				steps[maze[i][j]].x=j;
				if(maze[i][j]>max)
					max=maze[i][j];
				printf(" ");
			}
			else if(maze[i][j]==END)
			{
				end.y=i;
				end.x=j;
				printf("D");
			}
			else
				printf(" ");
		}
		printf("\n");
	}
	SetConsoleTextAttribute(hConsoleOut, FOREGROUND_RED|FOREGROUND_INTENSITY);
	if(_x*_y>=2000)
		speed=25;
	if(_x*_y>=5000)
		speed=10;
	for(i=1;i<=max;i++)
	{
		gotoxy(steps[i].x,steps[i].y);
		printf("*");
		Sleep(speed);
	}
	gotoxy(end.x,end.y);
	printf("Y");
	SetConsoleTextAttribute(hConsoleOut,FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
	return ;
}

int move(int n)
{
	int i,j;
	if(maze[explorer.y][explorer.x]==END)
	{
		print_solution();
		gotoxy(_x+1,_y);
		printf("\nPress Enter to exit.");
		getchar();
		exit(0);
	}
	maze[explorer.y][explorer.x]=n;
	for(i=0;i<4;i++)
	{
		if(can_move(explorer.y+direction[i].y,explorer.x+direction[i].x))
		{
			explorer.y+=direction[i].y;
			explorer.x+=direction[i].x;
			move(n+1);
			maze[explorer.y][explorer.x]=NOTWAY;
			explorer.y-=direction[i].y;
			explorer.x-=direction[i].x;
		}
	}
	maze[explorer.y][explorer.x]=NOTWAY;
}

int is_map_created()
{
	int i,j,x,y;
	x=_x;
	y=_y;
	for(i=1;i<y-1;i+=2)
		for(j=1;j<x-1;j+=2)
			if(maze[i][j]==0)
			{
				temp.y=i;
				temp.x=j;
				return 0;
			}
	return 1;
}

int can_go(int x,int y)
{
	if(x<1||y<1||x>=_x||y>=_y)
		return 0;
	else if(maze[y][x]>0)
		return 0;
	return 1;
}

int can_set(int x,int y)
{
	if(x<1||y<1||x>=_x||y>=_y)
		return 0;
	else if(maze[y][x]<1)
		return 0;
	return 1;
}

void print_maze()
{
	int i,j,x,y;
	x=_x;
	y=_y;
	for(i=0;i<y;i++)
	{
		for(j=0;j<x;j++)
		{
			if(maze[i][j]==WALL)
			{
				printf("#");
			}
			else
				printf(" ");
		}
		printf("\n");
	}
}

int make_map()
{
	int step,i,direction_random,count=0;
	maze[maker.y][maker.x]=sign;
	for(i=0;i<4;i++)
	{
		if(can_go(maker.x+2*direction[i].x,maker.y+2*direction[i].y))
		{
			count++;
		}
	}
	if(count==0)
		return 0;
	step=rand()%3+1;
	direction_random=rand()%4;
	for(i=0;i<step;i++)
	{
		if(can_go(maker.x+2*direction[direction_random].x,maker.y+2*direction[direction_random].y))
		{
			maze[maker.y+direction[direction_random].y][maker.x+direction[direction_random].x]=sign;
			maze[maker.y+2*direction[direction_random].y][maker.x+2*direction[direction_random].x]=sign;
			maker.x+=2*direction[direction_random].x;
			maker.y+=2*direction[direction_random].y;
		}
		else
		{
			direction_random=rand()%4;
		}
	}
	return 1;
}

int complete_map(void)
{
	int i;
	for(i=0;i<4;i++)
	{
		if(can_set(maker.x+2*direction[i].x,maker.y+2*direction[i].y))
		{
			maze[maker.y+direction[i].y][maker.x+direction[i].x]=sign+1;
			return 1;
		}
	}
	return 0;
}

int main(int argc,char *argv[])
{
	int i,j,x,y,s,e,*p_temp;
	char num[10];
	HANDLE    hConsoleOut;
	hConsoleOut = GetStdHandle(STD_OUTPUT_HANDLE);
	if(argc>=3)
	{
		_y=2*atoi(argv[2])+1;
		_x=2*atoi(argv[1])+1;
	}
	else if(argc==2)
	{
		_y=_x=2*atoi(argv[1])+1;
	}
	else
	{
		_y=_Y;
		_x=_X;
	}
	if(_y<1||_x<1||_x>79||_y>300)
	{
		printf("Error!"); 
		return 1;
	}
	maze=(int **)calloc(_y,sizeof(int *));
	p_temp=(int *)calloc(_x*_y,sizeof(int));
	for(i=0;i<_y;i++)
	{
		maze[i]=p_temp+i*_x;
	}
	x=_x;
	y=_y;
	cls(hConsoleOut);
	for(i=0;i<y;i++)
	{
		for(j=0;j<x;j++)
		{
			maze[i][j]=!(j%2)||!(i%2)||i==0||i==y-1?WALL:0;
		}
	}
	maker.y=1;
	maker.x=1;
	srand(time(NULL));
	while(!is_map_created())
	{
		while(make_map())
			;
		sign++;
		maker=temp;
		if(sign>=3)
			complete_map();
	}
	maker=temp;
	if(sign>=3)
		complete_map();
	for(i=0;i<y;i++)
		for(j=0;j<x;j++)
			if(maze[i][j]>0)
				maze[i][j]=0;
	srand(time(NULL));
	s=rand()%(x-2)+1;
	e=rand()%(x-2)+1;
	explorer.x=s;
	explorer.y=0;
	maze[0][s]=START;
	maze[y-1][e]=END;
	move(1);
	printf("Error!\n");
	return 1;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

/* Name: Maze-In-Console

* ############################################

* Author: LLonely

* ID: xxx（删掉了）

* Email: i#llonely.com

* Website: llonely.com

* --------------------------------------------

* Maze-Core & Maze-Console-Dynamic-Expression & Maze-Random-Generator

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#include<windows.h>

#define WALL -1

#define START -3

#define END -4

#define NOTWAY -2

#define MX 39

#define MY 149

#define _Y (MY*2+1)

#define _X (MX*2+1)

#define PERR(bSuccess, api){if(!(bSuccess)) printf("%s:Error %d from %s \

on line %d\n", __FILE__, GetLastError(), api, __LINE__);}

// int maze[MY*2+1][MX*2+1],sign=1,_x=0,_y=0;

int **maze,sign=1,_x=0,_y=0;

unsigned long speed=50;

struct position

{

int x;

int y;

}direction[]={{1,0},{-1,0},{0,1},{0,-1}},maker,temp,explorer;

void gotoxy(int x, int y)

{

CONSOLE_SCREEN_BUFFER_INFO csbiInfo;

HANDLE hConsoleOut;

hConsoleOut = GetStdHandle(STD_OUTPUT_HANDLE);

GetConsoleScreenBufferInfo(hConsoleOut, &csbiInfo);

csbiInfo.dwCursorPosition.X = x;

csbiInfo.dwCursorPosition.Y = y;

SetConsoleCursorPosition(hConsoleOut, csbiInfo.dwCursorPosition);

}

void cls(HANDLE hConsole)

{

COORD coordScreen = { 0, 0 };

BOOL bSuccess;

DWORD cCharsWritten;

CONSOLE_SCREEN_BUFFER_INFO csbi;

DWORD dwConSize;

bSuccess = GetConsoleScreenBufferInfo( hConsole, &csbi );

PERR( bSuccess, "GetConsoleScreenBufferInfo" );

dwConSize = csbi.dwSize.X * csbi.dwSize.Y;

bSuccess = FillConsoleOutputCharacter( hConsole, (TCHAR) ' ',

dwConSize, coordScreen, &cCharsWritten );

PERR( bSuccess, "FillConsoleOutputCharacter" );

bSuccess = GetConsoleScreenBufferInfo( hConsole, &csbi );

PERR( bSuccess, "ConsoleScreenBufferInfo" );

bSuccess = FillConsoleOutputAttribute( hConsole, csbi.wAttributes,

dwConSize, coordScreen, &cCharsWritten );

PERR( bSuccess, "FillConsoleOutputAttribute" );

bSuccess = SetConsoleCursorPosition( hConsole, coordScreen );

PERR( bSuccess, "SetConsoleCursorPosition" );

return;

}

int can_move(int y,int x)

{

if(y<0||x<0||x>=_x||y>=_y)

return 0;

else if(maze[y][x]==WALL||maze[y][x]==NOTWAY||maze[y][x]==START||maze[y][x]>0)

return 0;

else

return 1;

}

void print_solution(void)

{

int i,j,max=0;

HANDLE hConsoleOut;

hConsoleOut = GetStdHandle(STD_OUTPUT_HANDLE);

/* struct step

{

int y;

int x;

}steps[_X*_Y+1],end;*/

struct step

{

int y;

int x;

}*steps,end;

steps=(struct step*)calloc(_y*_x+1,sizeof(struct step));

for(i=0;i<_y;i++)

{

for(j=0;j<_x;j++)

{

if(maze[i][j]==WALL)

printf("%c",'#');

else if(maze[i][j]>0)

{

steps[maze[i][j]].y=i;

steps[maze[i][j]].x=j;

if(maze[i][j]>max)

max=maze[i][j];

printf(" ");

}

else if(maze[i][j]==END)

{

end.y=i;

end.x=j;

printf("D");

}

else

printf(" ");

}

printf("\n");

}

SetConsoleTextAttribute(hConsoleOut, FOREGROUND_RED|FOREGROUND_INTENSITY);

if(_x*_y>=2000)

speed=25;

if(_x*_y>=5000)

speed=10;

for(i=1;i<=max;i++)

{

gotoxy(steps[i].x,steps[i].y);

printf("*");

Sleep(speed);

}

gotoxy(end.x,end.y);

printf("Y");

SetConsoleTextAttribute(hConsoleOut,FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);

return ;

}

int move(int n)

{

int i,j;

if(maze[explorer.y][explorer.x]==END)

{

print_solution();

gotoxy(_x+1,_y);

printf("\nPress Enter to exit.");

getchar();

exit(0);

}

maze[explorer.y][explorer.x]=n;

for(i=0;i<4;i++)

{

if(can_move(explorer.y+direction[i].y,explorer.x+direction[i].x))

{

explorer.y+=direction[i].y;

explorer.x+=direction[i].x;

move(n+1);

maze[explorer.y][explorer.x]=NOTWAY;

explorer.y-=direction[i].y;

explorer.x-=direction[i].x;

}

maze[explorer.y][explorer.x]=NOTWAY;

}

int is_map_created()

{

int i,j,x,y;

x=_x;

y=_y;

for(i=1;i<y-1;i+=2)

for(j=1;j<x-1;j+=2)

if(maze[i][j]==0)

{

temp.y=i;

temp.x=j;

return 0;

}

return 1;

}

int can_go(int x,int y)

{

if(x<1||y<1||x>=_x||y>=_y)

return 0;

else if(maze[y][x]>0)

return 0;

return 1;

}

int can_set(int x,int y)

{

if(x<1||y<1||x>=_x||y>=_y)

return 0;

else if(maze[y][x]<1)

return 0;

return 1;

}

void print_maze()

{

int i,j,x,y;

x=_x;

y=_y;

for(i=0;i<y;i++)

{

for(j=0;j<x;j++)

{

if(maze[i][j]==WALL)

{

printf("#");

}

else

printf(" ");

}

printf("\n");

}

int make_map()

{

int step,i,direction_random,count=0;

maze[maker.y][maker.x]=sign;

for(i=0;i<4;i++)

{

if(can_go(maker.x+2*direction[i].x,maker.y+2*direction[i].y))

{

count++;

}

if(count==0)

return 0;

step=rand()%3+1;

direction_random=rand()%4;

for(i=0;i<step;i++)

{

if(can_go(maker.x+2*direction[direction_random].x,maker.y+2*direction[direction_random].y))

{

maze[maker.y+direction[direction_random].y][maker.x+direction[direction_random].x]=sign;

maze[maker.y+2*direction[direction_random].y][maker.x+2*direction[direction_random].x]=sign;

maker.x+=2*direction[direction_random].x;

maker.y+=2*direction[direction_random].y;

}

else

{

direction_random=rand()%4;

}

return 1;

}

int complete_map(void)

{

int i;

for(i=0;i<4;i++)

{

if(can_set(maker.x+2*direction[i].x,maker.y+2*direction[i].y))

{

maze[maker.y+direction[i].y][maker.x+direction[i].x]=sign+1;

return 1;

}

return 0;

}

int main(int argc,char *argv[])

{

int i,j,x,y,s,e,*p_temp;

char num[10];

HANDLE hConsoleOut;

hConsoleOut = GetStdHandle(STD_OUTPUT_HANDLE);

if(argc>=3)

{

_y=2*atoi(argv[2])+1;

_x=2*atoi(argv[1])+1;

}

else if(argc==2)

{

_y=_x=2*atoi(argv[1])+1;

}

else

{

_y=_Y;

_x=_X;

}

if(_y<1||_x<1||_x>79||_y>300)

{

printf("Error!");

return 1;

}

maze=(int **)calloc(_y,sizeof(int *));

p_temp=(int *)calloc(_x*_y,sizeof(int));

for(i=0;i<_y;i++)

{

maze[i]=p_temp+i*_x;

}

x=_x;

y=_y;

cls(hConsoleOut);

for(i=0;i<y;i++)

{

for(j=0;j<x;j++)

{

maze[i][j]=!(j%2)||!(i%2)||i==0||i==y-1?WALL:0;

}

maker.y=1;

maker.x=1;

srand(time(NULL));

while(!is_map_created())

{

while(make_map())

;

sign++;

maker=temp;

if(sign>=3)

complete_map();

}

maker=temp;

if(sign>=3)

complete_map();

for(i=0;i<y;i++)

for(j=0;j<x;j++)

if(maze[i][j]>0)

maze[i][j]=0;

srand(time(NULL));

s=rand()%(x-2)+1;

e=rand()%(x-2)+1;

explorer.x=s;

explorer.y=0;

maze[0][s]=START;

maze[y-1][e]=END;

move(1);

printf("Error!\n");

return 1;

}

GUI 版（还有一个 Res 目录存放了实现动画的图片）

/* Name: Maze-With-Gui
 * ############################################
 * Author: LLonely
 * ID: Deleted
 * Email: i#llonely.com
 * Website: llonely.com
 * Powered by Ege Gprahics
 */
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#include "graphics.h"
#define WALL -1
#define START -3
#define END -4
#define NOTWAY -2
#define MX 60
#define MY 60
#define _Y (MY*2+1)
#define _X (MX*2+1)
// int maze[MY * 2 + 1][MX * 2 + 1], sign = 1, sign_old;
int ** maze, sign = 1;
int _x, _y, mx, my;
struct position
{
	int x;
	int y;
}direction[] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }, maker, temp, explorer;

int can_move(int y, int x)
{
	if (y<0 || x<0 || x >= _x || y >= _x)
		return 0;
	else if (maze[y][x] == WALL || maze[y][x] == NOTWAY || maze[y][x] == START || maze[y][x]>0)
		return 0;
	else
		return 1;
}
int draw_arrow(int x, int y, int r, int direction)
{
	switch (direction)
	{
	case 0:
		line(x - r, y, x + r, y);
		line(x, y - r, x + r, y);
		line(x, y + r, x + r, y);
		break;
	case 1:
		line(x - r, y, x + r, y);
		line(x, y - r, x - r, y);
		line(x, y + r, x - r, y);
		break;
	case 2:
		line(x, y - r, x, y + r);
		line(x - r, y, x, y + r);
		line(x + r, y, x, y + r);
		break;
	case 3:
		line(x, y - r, x, y + r);
		line(x - r, y, x, y - r);
		line(x + r, y, x, y - r);
		break;
	default:
		return 0;
		break;
	}
	return 1;
}
void printf_pad(void)
{
	int i, j;
	int max = 0;
	int x, y;
	char res[20] = "res/res-1.png";
	/*	struct step
	{
	int y;
	int x;
	}steps[_x*_x + 1], end;*/
	struct step
	{
		int y;
		int x;
	}*steps, end;
	steps = (struct step *)malloc((_x*_x + 1)*sizeof(struct step));
	x = mx * 2 + 1;
	y = my * 2 + 1;
	initgraph(605, 605);
	setbkcolor(WHITE);
	setcolor(BLACK);
	setcaption("Maze");
	for (j = 0; j < y; j += 2)
	for (i = 1; i < x - 1; i += 2)
	if (maze[j][i] == WALL)
		line(2 + (i / 2) * 600.0 / mx, 2 + (j / 2) * 600.0 / mx, 2 + (i / 2 + 1) * 600.0 / mx, 2 + (j / 2) * 600.0 / mx);
	for (j = 0; j < x; j += 2)
	for (i = 1; i < y - 1; i += 2)
	if (maze[i][j] == WALL)
		line(2 + (j / 2) * 600.0 / mx, 2 + (i / 2) * 600.0 / mx, 2 + (j / 2) * 600.0 / mx, 2 + (i / 2 + 1) * 600.0 / mx);

	for (i = 0; i<_x; i++)
	{
		for (j = 0; j<_x; j++)
		{
			if (maze[i][j] == WALL)
				;
			else if (maze[i][j]>0)
			{
				steps[maze[i][j]].y = i;
				steps[maze[i][j]].x = j;
				if (maze[i][j]>max)
					max = maze[i][j];
			}
			else if (maze[i][j] == END)
			{
				end.y = i;
				end.x = j;
				steps[max + 1].y = i;
				steps[max + 1].x = j;
			}
			else
				;
		}
	}
	setcolor(RED);
	for (i = 1; i <= max; i++)
	{
		if (steps[i].x % 2 && steps[i].y % 2)
		{
			for (j = 0; j < 4; j++)
			{
				if (steps[i].x + direction[j].x == steps[i + 1].x&&steps[i].y + direction[j].y == steps[i + 1].y)
					break;
			}
			draw_arrow(2 + 600.0 / my / 2 * 0.1 + (steps[i].x)*(600.0 / mx / 2), 2 + 600.0 / my / 2 * 0.1 + (steps[i].y)*(600.0 / my / 2), 600.0 / my / 2 * 0.9, j);
			//circle(2 + 600.0 / my / 2 * 0.1 + (steps[i].x)*(600.0 / mx / 2), 2 + 600.0 / my / 2 * 0.1+ (steps[i].y)*(600.0 / my / 2), 600.0 / my / 2 * 0.9);
			Sleep(20);
		}
	}
	PIMAGE image[6], screen;
	screen = newimage();
	getimage(screen, 0, 0, 605, 605);
	for (i = 0; i < 6; i++)
	{
		image[i] = newimage();
		getimage(image[i], res, 0, 0);
		res[8] += 1;
	}
	setfont(60, 0, "宋体");
	setbkmode(TRANSPARENT);
	settextjustify(CENTER_TEXT, CENTER_TEXT);
	for (i = 0; i < 4; i++)
	{
		for (j = 0; j < 6; j++)
		{
			setfont(60 + ((j == 2 || j == 5) ? 0 : 1) * 10, 0, "宋体");
			outtextxy(303, 250, "SUCCESS");
			putimage_withalpha(NULL, image[j], 100, 305);
			//putimage(100, 200, image[j], SRCINVERT);
			if (j == 2 || j == 5)
				Sleep(150);
			Sleep(200);
			//cleardevice();
			putimage(0, 0, screen);
		}
	}
	putimage(0, 0, screen);
	getch();
	closegraph();
	return;
}

int move(int n)
{
	int i;
	if (maze[explorer.y][explorer.x] == END)
	{
		printf_pad();
		//getchar();
		exit(0);
	}
	maze[explorer.y][explorer.x] = n;
	for (i = 0; i<4; i++)
	{
		if (can_move(explorer.y + direction[i].y, explorer.x + direction[i].x))
		{
			explorer.y += direction[i].y;
			explorer.x += direction[i].x;
			move(n + 1);
			maze[explorer.y][explorer.x] = NOTWAY;
			explorer.y -= direction[i].y;
			explorer.x -= direction[i].x;
		}
	}
	maze[explorer.y][explorer.x] = NOTWAY;
	return 0;
}
int is_map_created()
{
	int i, j, x, y;
	x = mx * 2 + 1;
	y = my * 2 + 1;
	for (i = 1; i<y - 1; i += 2)
	for (j = 1; j<x - 1; j += 2)
	if (maze[i][j] == 0)
	{
		temp.y = i;
		temp.x = j;
		return 0;
	}
	return 1;
}

int can_go(int x, int y)
{
	if (x<1 || y<1 || x >= mx * 2 + 1 || y >= my * 2 + 1)
		return 0;
	else if (maze[y][x]>0)
		return 0;
	return 1;
}

int can_set(int x, int y)
{
	if (x<1 || y<1 || x >= mx * 2 || y >= my * 2)
		return 0;
	else if (maze[y][x]<1)
		return 0;
	return 1;
}

void print_maze()
{
	int i, j, x, y;
	x = mx * 2 + 1;
	y = my * 2 + 1;
	for (i = 0; i<y; i++)
	{
		for (j = 0; j<x; j++)
		{
			if (maze[i][j] == WALL)
			{
				printf("#");
			}
			else
				printf(" ");
		}
		printf("\n");
	}
}

int make_map()
{
	int step, i, direction_temp, count = 0, d;
	maze[maker.y][maker.x] = sign;
	for (i = 0; i<4; i++)
	{
		if (can_go(maker.x + 2 * direction[i].x, maker.y + 2 * direction[i].y))
		{
			count++;
		}
	}
	if (count == 0)
		return 0;
	step = rand() % 3 + 1;
	direction_temp = rand() % 4;
	for (i = 0; i<step; i++)
	{
		if (can_go(maker.x + 2 * direction[direction_temp].x, maker.y + 2 * direction[direction_temp].y))
		{
			maze[maker.y + direction[direction_temp].y][maker.x + direction[direction_temp].x] = sign;
			maze[maker.y + 2 * direction[direction_temp].y][maker.x + 2 * direction[direction_temp].x] = sign;
			maker.x += 2 * direction[direction_temp].x;
			maker.y += 2 * direction[direction_temp].y;

		}
		else
		{
			d = rand() % 4;
			direction_temp = d;
		}
	}
	return 1;
}

int com_map()
{
	int i;
	for (i = 0; i<4; i++)
	{
		if (can_set(maker.x + 2 * direction[i].x, maker.y + 2 * direction[i].y))
		{
			maze[maker.y + direction[i].y][maker.x + direction[i].x] = sign + 1;
			return 1;
		}
	}
	return 0;
}
int main()
{
	int i, j, x, y, s, e;
	int *p_temp;
	char str[10];
	setinitmode(NULL);
	initgraph(400, 300);
	setcaption("MAZE");
	inputbox_getline("请输入迷宫的大小","请输入一个数字，输入完请回车",str,sizeof(str) / sizeof(*str));
	mx = my = atoi(str);
	if (mx<1 || mx>200)
	{
		mx = MX;
		my = MY;
		_x = _X;
		_y = _Y;
	}
	else
	{
		_x = mx * 2 + 1;
		_y = my * 2 + 1;
	}
	x = mx * 2 + 1;
	y = my * 2 + 1;
	closegraph();
	maze = (int **)calloc(y, sizeof(int *));
	p_temp = (int *)calloc(x*y, sizeof(int));
	for (i = 0; i<y; i++)
	{
		maze[i] = p_temp + x*i;
	}
	for (i = 0; i<y; i++)
	{
		for (j = 0; j<x; j++)
		{
			maze[i][j] = !(j % 2) || !(i % 2) || i == 0 || i == y - 1 ? WALL : 0;
		}
	}
	maker.y = 1;
	maker.x = 1;
	srand(time(NULL));
	while (!is_map_created())
	{
		while (make_map())
			;
		sign++;
		maker = temp;
		if (sign >= 3)
			com_map();
	}
	maker = temp;
	if (sign >= 3)
		com_map();
	//print_maze();
	for (i = 0; i<y; i++)
	for (j = 0; j<x; j++)
	if (maze[i][j]>0)
		maze[i][j] = 0;
	srand(time(NULL));
	s = rand() % (mx);
	e = rand() % (mx);
	explorer.x = 2 * s + 1;
	explorer.y = 0;
	maze[0][2 * s + 1] = START;
	maze[y - 1][2 * e + 1] = END;
	move(1);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

/* Name: Maze-With-Gui

* ############################################

* Author: LLonely

* ID: Deleted

* Email: i#llonely.com

* Website: llonely.com

* Powered by Ege Gprahics

#include<stdlib.h>

#include<stdio.h>

#include<time.h>

#include "graphics.h"

#define WALL -1

#define START -3

#define END -4

#define NOTWAY -2

#define MX 60

#define MY 60

#define _Y (MY*2+1)

#define _X (MX*2+1)

// int maze[MY * 2 + 1][MX * 2 + 1], sign = 1, sign_old;

int ** maze, sign = 1;

int _x, _y, mx, my;

struct position

{

int x;

int y;

}direction[] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }, maker, temp, explorer;

int can_move(int y, int x)

{

if (y<0 || x<0 || x >= _x || y >= _x)

return 0;

else if (maze[y][x] == WALL || maze[y][x] == NOTWAY || maze[y][x] == START || maze[y][x]>0)

return 0;

else

return 1;

}

int draw_arrow(int x, int y, int r, int direction)

{

switch (direction)

{

case 0:

line(x - r, y, x + r, y);

line(x, y - r, x + r, y);

line(x, y + r, x + r, y);

break;

case 1:

line(x - r, y, x + r, y);

line(x, y - r, x - r, y);

line(x, y + r, x - r, y);

break;

case 2:

line(x, y - r, x, y + r);

line(x - r, y, x, y + r);

line(x + r, y, x, y + r);

break;

case 3:

line(x, y - r, x, y + r);

line(x - r, y, x, y - r);

line(x + r, y, x, y - r);

break;

default:

return 0;

break;

}

return 1;

}

void printf_pad(void)

{

int i, j;

int max = 0;

int x, y;

char res[20] = "res/res-1.png";

/* struct step

{

int y;

int x;

}steps[_x*_x + 1], end;*/

struct step

{

int y;

int x;

}*steps, end;

steps = (struct step *)malloc((_x*_x + 1)*sizeof(struct step));

x = mx * 2 + 1;

y = my * 2 + 1;

initgraph(605, 605);

setbkcolor(WHITE);

setcolor(BLACK);

setcaption("Maze");

for (j = 0; j < y; j += 2)

for (i = 1; i < x - 1; i += 2)

if (maze[j][i] == WALL)

line(2 + (i / 2) * 600.0 / mx, 2 + (j / 2) * 600.0 / mx, 2 + (i / 2 + 1) * 600.0 / mx, 2 + (j / 2) * 600.0 / mx);

for (j = 0; j < x; j += 2)

for (i = 1; i < y - 1; i += 2)

if (maze[i][j] == WALL)

line(2 + (j / 2) * 600.0 / mx, 2 + (i / 2) * 600.0 / mx, 2 + (j / 2) * 600.0 / mx, 2 + (i / 2 + 1) * 600.0 / mx);

for (i = 0; i<_x; i++)

{

for (j = 0; j<_x; j++)

{

if (maze[i][j] == WALL)

;

else if (maze[i][j]>0)

{

steps[maze[i][j]].y = i;

steps[maze[i][j]].x = j;

if (maze[i][j]>max)

max = maze[i][j];

}

else if (maze[i][j] == END)

{

end.y = i;

end.x = j;

steps[max + 1].y = i;

steps[max + 1].x = j;

}

else

;

}

setcolor(RED);

for (i = 1; i <= max; i++)

{

if (steps[i].x % 2 && steps[i].y % 2)

{

for (j = 0; j < 4; j++)

{

if (steps[i].x + direction[j].x == steps[i + 1].x&&steps[i].y + direction[j].y == steps[i + 1].y)

break;

}

draw_arrow(2 + 600.0 / my / 2 * 0.1 + (steps[i].x)*(600.0 / mx / 2), 2 + 600.0 / my / 2 * 0.1 + (steps[i].y)*(600.0 / my / 2), 600.0 / my / 2 * 0.9, j);

//circle(2 + 600.0 / my / 2 * 0.1 + (steps[i].x)*(600.0 / mx / 2), 2 + 600.0 / my / 2 * 0.1+ (steps[i].y)*(600.0 / my / 2), 600.0 / my / 2 * 0.9);

Sleep(20);

}

PIMAGE image[6], screen;

screen = newimage();

getimage(screen, 0, 0, 605, 605);

for (i = 0; i < 6; i++)

{

image[i] = newimage();

getimage(image[i], res, 0, 0);

res[8] += 1;

}

setfont(60, 0, "宋体");

setbkmode(TRANSPARENT);

settextjustify(CENTER_TEXT, CENTER_TEXT);

for (i = 0; i < 4; i++)

{

for (j = 0; j < 6; j++)

{

setfont(60 + ((j == 2 || j == 5) ? 0 : 1) * 10, 0, "宋体");

outtextxy(303, 250, "SUCCESS");

putimage_withalpha(NULL, image[j], 100, 305);

//putimage(100, 200, image[j], SRCINVERT);

if (j == 2 || j == 5)

Sleep(150);

Sleep(200);

//cleardevice();

putimage(0, 0, screen);

}

putimage(0, 0, screen);

getch();

closegraph();

return;

}

int move(int n)

{

int i;

if (maze[explorer.y][explorer.x] == END)

{

printf_pad();

//getchar();

exit(0);

}

maze[explorer.y][explorer.x] = n;

for (i = 0; i<4; i++)

{

if (can_move(explorer.y + direction[i].y, explorer.x + direction[i].x))

{

explorer.y += direction[i].y;

explorer.x += direction[i].x;

move(n + 1);

maze[explorer.y][explorer.x] = NOTWAY;

explorer.y -= direction[i].y;

explorer.x -= direction[i].x;

}

maze[explorer.y][explorer.x] = NOTWAY;

return 0;

}

int is_map_created()

{

int i, j, x, y;

x = mx * 2 + 1;

y = my * 2 + 1;

for (i = 1; i<y - 1; i += 2)

for (j = 1; j<x - 1; j += 2)

if (maze[i][j] == 0)

{

temp.y = i;

temp.x = j;

return 0;

}

return 1;

}

int can_go(int x, int y)

{

if (x<1 || y<1 || x >= mx * 2 + 1 || y >= my * 2 + 1)

return 0;

else if (maze[y][x]>0)

return 0;

return 1;

}

int can_set(int x, int y)

{

if (x<1 || y<1 || x >= mx * 2 || y >= my * 2)

return 0;

else if (maze[y][x]<1)

return 0;

return 1;

}

void print_maze()

{

int i, j, x, y;

x = mx * 2 + 1;

y = my * 2 + 1;

for (i = 0; i<y; i++)

{

for (j = 0; j<x; j++)

{

if (maze[i][j] == WALL)

{

printf("#");

}

else

printf(" ");

}

printf("\n");

}

int make_map()

{

int step, i, direction_temp, count = 0, d;

maze[maker.y][maker.x] = sign;

for (i = 0; i<4; i++)

{

if (can_go(maker.x + 2 * direction[i].x, maker.y + 2 * direction[i].y))

{

count++;

}

if (count == 0)

return 0;

step = rand() % 3 + 1;

direction_temp = rand() % 4;

for (i = 0; i<step; i++)

{

if (can_go(maker.x + 2 * direction[direction_temp].x, maker.y + 2 * direction[direction_temp].y))

{

maze[maker.y + direction[direction_temp].y][maker.x + direction[direction_temp].x] = sign;

maze[maker.y + 2 * direction[direction_temp].y][maker.x + 2 * direction[direction_temp].x] = sign;

maker.x += 2 * direction[direction_temp].x;

maker.y += 2 * direction[direction_temp].y;

}

else

{

d = rand() % 4;

direction_temp = d;

}

return 1;

}

int com_map()

{

int i;

for (i = 0; i<4; i++)

{

if (can_set(maker.x + 2 * direction[i].x, maker.y + 2 * direction[i].y))

{

maze[maker.y + direction[i].y][maker.x + direction[i].x] = sign + 1;

return 1;

}

return 0;

}

int main()

{

int i, j, x, y, s, e;

int *p_temp;

char str[10];

setinitmode(NULL);

initgraph(400, 300);

setcaption("MAZE");

inputbox_getline("请输入迷宫的大小","请输入一个数字，输入完请回车",str,sizeof(str) / sizeof(*str));

mx = my = atoi(str);

if (mx<1 || mx>200)

{

mx = MX;

my = MY;

_x = _X;

_y = _Y;

}

else

{

_x = mx * 2 + 1;

_y = my * 2 + 1;

}

x = mx * 2 + 1;

y = my * 2 + 1;

closegraph();

maze = (int **)calloc(y, sizeof(int *));

p_temp = (int *)calloc(x*y, sizeof(int));

for (i = 0; i<y; i++)

{

maze[i] = p_temp + x*i;

}

for (i = 0; i<y; i++)

{

for (j = 0; j<x; j++)

{

maze[i][j] = !(j % 2) || !(i % 2) || i == 0 || i == y - 1 ? WALL : 0;

}

maker.y = 1;

maker.x = 1;

srand(time(NULL));

while (!is_map_created())

{

while (make_map())

;

sign++;

maker = temp;

if (sign >= 3)

com_map();

}

maker = temp;

if (sign >= 3)

com_map();

//print_maze();

for (i = 0; i<y; i++)

for (j = 0; j<x; j++)

if (maze[i][j]>0)

maze[i][j] = 0;

srand(time(NULL));

s = rand() % (mx);

e = rand() % (mx);

explorer.x = 2 * s + 1;

explorer.y = 0;

maze[0][2 * s + 1] = START;

maze[y - 1][2 * e + 1] = END;

move(1);

return 0;

}

采用 DFS 的 GUI 版

#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#include "graphics.h"
#define WALL -1
#define START -3
#define END -4
#define NOTWAY -2
#define MX 60
#define MY 60
#define _Y (MY*2+1)
#define _X (MX*2+1)
// int maze[MY * 2 + 1][MX * 2 + 1], sign = 1, sign_old;
int ** maze, sign = 1, maker_n = 1, *maker_step, i_maker_step = -1;
int _x, _y, mx, my;
struct position
{
	int x;
	int y;
}direction[] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }, maker, temp, explorer;

int can_move(int y, int x)
{
	if (y<0 || x<0 || x >= _x || y >= _x)
		return 0;
	else if (maze[y][x] == WALL || maze[y][x] == NOTWAY || maze[y][x] == START || maze[y][x]>0)
		return 0;
	else
		return 1;
}
int draw_arrow(int x, int y, int r, int direction)
{
	switch (direction)
	{
	case 0:
		line(x - r, y, x + r, y);
		line(x, y - r, x + r, y);
		line(x, y + r, x + r, y);
		break;
	case 1:
		line(x - r, y, x + r, y);
		line(x, y - r, x - r, y);
		line(x, y + r, x - r, y);
		break;
	case 2:
		line(x, y - r, x, y + r);
		line(x - r, y, x, y + r);
		line(x + r, y, x, y + r);
		break;
	case 3:
		line(x, y - r, x, y + r);
		line(x - r, y, x, y - r);
		line(x + r, y, x, y - r);
		break;
	default:
		return 0;
		break;
	}
	return 1;
}
void printf_pad(void)
{
	int i, j;
	int max = 0;
	int x, y;
	char res[20] = "res/res-1.png";
	/*	struct step
	{
	int y;
	int x;
	}steps[_x*_x + 1], end;*/
	struct step
	{
		int y;
		int x;
	}*steps, end;
	steps = (struct step *)malloc((_x*_x + 1)*sizeof(struct step));
	x = mx * 2 + 1;
	y = my * 2 + 1;
	initgraph(605, 605);
	setbkcolor(WHITE);
	setcolor(BLACK);
	setcaption("Maze");
	for (j = 0; j < y; j += 2)
	for (i = 1; i < x - 1; i += 2)
	if (maze[j][i] == WALL)
		line(2 + (i / 2) * 600.0 / mx, 2 + (j / 2) * 600.0 / mx, 2 + (i / 2 + 1) * 600.0 / mx, 2 + (j / 2) * 600.0 / mx);
	for (j = 0; j < x; j += 2)
	for (i = 1; i < y - 1; i += 2)
	if (maze[i][j] == WALL)
		line(2 + (j / 2) * 600.0 / mx, 2 + (i / 2) * 600.0 / mx, 2 + (j / 2) * 600.0 / mx, 2 + (i / 2 + 1) * 600.0 / mx);

	for (i = 0; i<_x; i++)
	{
		for (j = 0; j<_x; j++)
		{
			if (maze[i][j] == WALL)
				;
			else if (maze[i][j]>0)
			{
				steps[maze[i][j]].y = i;
				steps[maze[i][j]].x = j;
				if (maze[i][j]>max)
					max = maze[i][j];
			}
			else if (maze[i][j] == END)
			{
				end.y = i;
				end.x = j;
				steps[max + 1].y = i;
				steps[max + 1].x = j;
			}
			else
				;
		}
	}
	setcolor(RED);
	for (i = 1; i <= max; i++)
	{
		if (steps[i].x % 2 && steps[i].y % 2)
		{
			for (j = 0; j < 4; j++)
			{
				if (steps[i].x + direction[j].x == steps[i + 1].x&&steps[i].y + direction[j].y == steps[i + 1].y)
					break;
			}
			draw_arrow(2 + 600.0 / my / 2 * 0.1 + (steps[i].x)*(600.0 / mx / 2), 2 + 600.0 / my / 2 * 0.1 + (steps[i].y)*(600.0 / my / 2), 600.0 / my / 2 * 0.9, j);
			//circle(2 + 600.0 / my / 2 * 0.1 + (steps[i].x)*(600.0 / mx / 2), 2 + 600.0 / my / 2 * 0.1+ (steps[i].y)*(600.0 / my / 2), 600.0 / my / 2 * 0.9);
			Sleep(20);
		}
	}
	PIMAGE image[6], screen;
	screen = newimage();
	getimage(screen, 0, 0, 605, 605);
	for (i = 0; i < 6; i++)
	{
		image[i] = newimage();
		getimage(image[i], res, 0, 0);
		res[8] += 1;
	}
	setfont(60, 0, "宋体");
	setbkmode(TRANSPARENT);
	settextjustify(CENTER_TEXT, CENTER_TEXT);
	for (i = 0; i < 4; i++)
	{
		for (j = 0; j < 6; j++)
		{
			setfont(60 + ((j == 2 || j == 5) ? 0 : 1) * 10, 0, "宋体");
			outtextxy(303, 250, "SUCCESS");
			putimage_withalpha(NULL, image[j], 100, 305);
			//putimage(100, 200, image[j], SRCINVERT);
			if (j == 2 || j == 5)
				Sleep(150);
			Sleep(200);
			//cleardevice();
			putimage(0, 0, screen);
		}
	}
	putimage(0, 0, screen);
	getch();
	closegraph();
	return;
}

int move(int n)
{
	int i;
	if (maze[explorer.y][explorer.x] == END)
	{
		printf_pad();
		//getchar();
		exit(0);
	}
	maze[explorer.y][explorer.x] = n;
	for (i = 0; i<4; i++)
	{
		if (can_move(explorer.y + direction[i].y, explorer.x + direction[i].x))
		{
			explorer.y += direction[i].y;
			explorer.x += direction[i].x;
			move(n + 1);
			maze[explorer.y][explorer.x] = NOTWAY;
			explorer.y -= direction[i].y;
			explorer.x -= direction[i].x;
		}
	}
	maze[explorer.y][explorer.x] = NOTWAY;
	return 0;
}
int is_map_created()
{
	int i, j, x, y;
	x = mx * 2 + 1;
	y = my * 2 + 1;
	for (i = 1; i<y - 1; i += 2)
	for (j = 1; j<x - 1; j += 2)
	if (maze[i][j] == 0)
	{
		temp.y = i;
		temp.x = j;
		return 0;
	}
	return 1;
}

int can_go(int x, int y)
{
	if (x<1 || y<1 || x >= mx * 2 + 1 || y >= my * 2 + 1)
		return 0;
	else if (maze[y][x]>0)
		return 0;
	return 1;
}

int can_set(int x, int y)
{
	if (x<1 || y<1 || x >= mx * 2 || y >= my * 2)
		return 0;
	else if (maze[y][x]<1)
		return 0;
	return 1;
}

void print_maze()
{
	int i, j, x, y;
	x = mx * 2 + 1;
	y = my * 2 + 1;
	for (i = 0; i<y; i++)
	{
		for (j = 0; j<x; j++)
		{
			if (maze[i][j] == WALL)
			{
				printf("#");
			}
			else
				printf(" ");
		}
		printf("\n");
	}
}

int make_map()
{
	int step, i, direction_temp, count = 0, d;
	maze[maker.y][maker.x] = sign;
	for (i = 0; i<4; i++)
	{
		if (can_go(maker.x + 2 * direction[i].x, maker.y + 2 * direction[i].y))
		{
			count++;
		}
	}
	if (count == 0)
		return 0;
	step = rand() % 3 + 1;
	direction_temp = rand() % 4;
	for (i = 0; i<step; i++)
	{
		if (can_go(maker.x + 2 * direction[direction_temp].x, maker.y + 2 * direction[direction_temp].y))
		{
			maze[maker.y + direction[direction_temp].y][maker.x + direction[direction_temp].x] = sign;
			maze[maker.y + 2 * direction[direction_temp].y][maker.x + 2 * direction[direction_temp].x] = sign;
			maker.x += 2 * direction[direction_temp].x;
			maker.y += 2 * direction[direction_temp].y;

		}
		else
		{
			d = rand() % 4;
			direction_temp = d;
		}
	}
	return 1;
}

int com_map()
{
	int i;
	for (i = 0; i<4; i++)
	{
		if (can_set(maker.x + 2 * direction[i].x, maker.y + 2 * direction[i].y))
		{
			maze[maker.y + direction[i].y][maker.x + direction[i].x] = sign + 1;
			return 1;
		}
	}
	return 0;
}

int make_map_dps()
{
	int step, i, direction_temp, count = 0, d;
	maze[maker.y][maker.x] = 1;
	if (maker_n == 100)
	{
		printf_pad();
		getchar();
		closegraph();
		exit(0);
	}
	for (i = 0; i<4; i++)
	{
		if (can_go(maker.x + 2 * direction[i].x, maker.y + 2 * direction[i].y))
		{
			count++;
		}
	}
	if (count == 0)
		return 0;
	step = rand() % 3 + 1;
	direction_temp = rand() % 4;
	for (i = 0; i<step; i++)
	{
		if (can_go(maker.x + 2 * direction[direction_temp].x, maker.y + 2 * direction[direction_temp].y))
		{
			maze[maker.y + direction[direction_temp].y][maker.x + direction[direction_temp].x] = sign;
			maze[maker.y + 2 * direction[direction_temp].y][maker.x + 2 * direction[direction_temp].x] = sign;
			maker.x += 2 * direction[direction_temp].x;
			maker.y += 2 * direction[direction_temp].y;
			maker_step[++i_maker_step] = direction_temp + 1;
			maker_n++;
		}
		else
		{
			d = rand() % 4;
			direction_temp = d;
		}
	}
	return 1;
}

int move_back()
{
	int i;
	if (i_maker_step<0 || i_maker_step >= mx*my)
		exit(0);
	i = maker_step[i_maker_step--] - 1;
	maker.y = maker.y - 2 * direction[i].y;
	maker.x = maker.x - 2 * direction[i].x;
	return 1;
}
int main()
{
	int i, j, x, y, s, e, maker_total;
	int *p_temp;
	char str[10];
	setinitmode(NULL);
	initgraph(400, 300);
	setcaption("MAZE");
	inputbox_getline("请输入迷宫的大小", "请输入一个数字，输入完请回车", str, sizeof(str) / sizeof(*str));
	mx = my = atoi(str);
	if (mx<1 || mx>200)
	{
		mx = MX;
		my = MY;
		_x = _X;
		_y = _Y;
	}
	else
	{
		_x = mx * 2 + 1;
		_y = my * 2 + 1;
	}
	maker_total = mx*my;
	x = mx * 2 + 1;
	y = my * 2 + 1;
	closegraph();
	maker_step = (int *)calloc(mx*my, sizeof(int));
	maze = (int **)calloc(y, sizeof(int *));
	p_temp = (int *)calloc(x*y, sizeof(int));
	for (i = 0; i<y; i++)
	{
		maze[i] = p_temp + x*i;
	}
	for (i = 0; i<y; i++)
	{
		for (j = 0; j<x; j++)
		{
			maze[i][j] = !(j % 2) || !(i % 2) || i == 0 || i == y - 1 ? WALL : 0;
		}
	}
	maker.y = 1;
	maker.x = 1;
	srand(time(NULL));
	while (maker_n != maker_total)
	{
		while (make_map_dps())
			;
		move_back();
	}
	/*	while (!is_map_created())
	{
	while (make_map())
	;
	sign++;
	maker = temp;
	if (sign >= 3)
	com_map();
	}
	maker = temp;
	if (sign >= 3)
	com_map();*/
	for (i = 0; i<y; i++)
	for (j = 0; j<x; j++)
	if (maze[i][j]>0)
		maze[i][j] = 0;
	srand(time(NULL));
	s = rand() % (mx);
	e = rand() % (mx);
	explorer.x = 2 * s + 1;
	explorer.y = 0;
	maze[0][2 * s + 1] = START;
	maze[y - 1][2 * e + 1] = END;
	printf_pad();
	//move(1);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

#include<stdlib.h>

#include<stdio.h>

#include<time.h>

#include "graphics.h"

#define WALL -1

#define START -3

#define END -4

#define NOTWAY -2

#define MX 60

#define MY 60

#define _Y (MY*2+1)

#define _X (MX*2+1)

// int maze[MY * 2 + 1][MX * 2 + 1], sign = 1, sign_old;

int ** maze, sign = 1, maker_n = 1, *maker_step, i_maker_step = -1;

int _x, _y, mx, my;

struct position

{

int x;

int y;

}direction[] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }, maker, temp, explorer;

int can_move(int y, int x)

{

if (y<0 || x<0 || x >= _x || y >= _x)

return 0;

else if (maze[y][x] == WALL || maze[y][x] == NOTWAY || maze[y][x] == START || maze[y][x]>0)

return 0;

else

return 1;

}

int draw_arrow(int x, int y, int r, int direction)

{

switch (direction)

{

case 0:

line(x - r, y, x + r, y);

line(x, y - r, x + r, y);

line(x, y + r, x + r, y);

break;

case 1:

line(x - r, y, x + r, y);

line(x, y - r, x - r, y);

line(x, y + r, x - r, y);

break;

case 2:

line(x, y - r, x, y + r);

line(x - r, y, x, y + r);

line(x + r, y, x, y + r);

break;

case 3:

line(x, y - r, x, y + r);

line(x - r, y, x, y - r);

line(x + r, y, x, y - r);

break;

default:

return 0;

break;

}

return 1;

}

void printf_pad(void)

{

int i, j;

int max = 0;

int x, y;

char res[20] = "res/res-1.png";

/* struct step

{

int y;

int x;

}steps[_x*_x + 1], end;*/

struct step

{

int y;

int x;

}*steps, end;

steps = (struct step *)malloc((_x*_x + 1)*sizeof(struct step));

x = mx * 2 + 1;

y = my * 2 + 1;

initgraph(605, 605);

setbkcolor(WHITE);

setcolor(BLACK);

setcaption("Maze");

for (j = 0; j < y; j += 2)

for (i = 1; i < x - 1; i += 2)

if (maze[j][i] == WALL)

line(2 + (i / 2) * 600.0 / mx, 2 + (j / 2) * 600.0 / mx, 2 + (i / 2 + 1) * 600.0 / mx, 2 + (j / 2) * 600.0 / mx);

for (j = 0; j < x; j += 2)

for (i = 1; i < y - 1; i += 2)

if (maze[i][j] == WALL)

line(2 + (j / 2) * 600.0 / mx, 2 + (i / 2) * 600.0 / mx, 2 + (j / 2) * 600.0 / mx, 2 + (i / 2 + 1) * 600.0 / mx);

for (i = 0; i<_x; i++)

{

for (j = 0; j<_x; j++)

{

if (maze[i][j] == WALL)

;

else if (maze[i][j]>0)

{

steps[maze[i][j]].y = i;

steps[maze[i][j]].x = j;

if (maze[i][j]>max)

max = maze[i][j];

}

else if (maze[i][j] == END)

{

end.y = i;

end.x = j;

steps[max + 1].y = i;

steps[max + 1].x = j;

}

else

;

}

setcolor(RED);

for (i = 1; i <= max; i++)

{

if (steps[i].x % 2 && steps[i].y % 2)

{

for (j = 0; j < 4; j++)

{

if (steps[i].x + direction[j].x == steps[i + 1].x&&steps[i].y + direction[j].y == steps[i + 1].y)

break;

}

draw_arrow(2 + 600.0 / my / 2 * 0.1 + (steps[i].x)*(600.0 / mx / 2), 2 + 600.0 / my / 2 * 0.1 + (steps[i].y)*(600.0 / my / 2), 600.0 / my / 2 * 0.9, j);

//circle(2 + 600.0 / my / 2 * 0.1 + (steps[i].x)*(600.0 / mx / 2), 2 + 600.0 / my / 2 * 0.1+ (steps[i].y)*(600.0 / my / 2), 600.0 / my / 2 * 0.9);

Sleep(20);

}

PIMAGE image[6], screen;

screen = newimage();

getimage(screen, 0, 0, 605, 605);

for (i = 0; i < 6; i++)

{

image[i] = newimage();

getimage(image[i], res, 0, 0);

res[8] += 1;

}

setfont(60, 0, "宋体");

setbkmode(TRANSPARENT);

settextjustify(CENTER_TEXT, CENTER_TEXT);

for (i = 0; i < 4; i++)

{

for (j = 0; j < 6; j++)

{

setfont(60 + ((j == 2 || j == 5) ? 0 : 1) * 10, 0, "宋体");

outtextxy(303, 250, "SUCCESS");

putimage_withalpha(NULL, image[j], 100, 305);

//putimage(100, 200, image[j], SRCINVERT);

if (j == 2 || j == 5)

Sleep(150);

Sleep(200);

//cleardevice();

putimage(0, 0, screen);

}

putimage(0, 0, screen);

getch();

closegraph();

return;

}

int move(int n)

{

int i;

if (maze[explorer.y][explorer.x] == END)

{

printf_pad();

//getchar();

exit(0);

}

maze[explorer.y][explorer.x] = n;

for (i = 0; i<4; i++)

{

if (can_move(explorer.y + direction[i].y, explorer.x + direction[i].x))

{

explorer.y += direction[i].y;

explorer.x += direction[i].x;

move(n + 1);

maze[explorer.y][explorer.x] = NOTWAY;

explorer.y -= direction[i].y;

explorer.x -= direction[i].x;

}

maze[explorer.y][explorer.x] = NOTWAY;

return 0;

}

int is_map_created()

{

int i, j, x, y;

x = mx * 2 + 1;

y = my * 2 + 1;

for (i = 1; i<y - 1; i += 2)

for (j = 1; j<x - 1; j += 2)

if (maze[i][j] == 0)

{

temp.y = i;

temp.x = j;

return 0;

}

return 1;

}

int can_go(int x, int y)

{

if (x<1 || y<1 || x >= mx * 2 + 1 || y >= my * 2 + 1)

return 0;

else if (maze[y][x]>0)

return 0;

return 1;

}

int can_set(int x, int y)

{

if (x<1 || y<1 || x >= mx * 2 || y >= my * 2)

return 0;

else if (maze[y][x]<1)

return 0;

return 1;

}

void print_maze()

{

int i, j, x, y;

x = mx * 2 + 1;

y = my * 2 + 1;

for (i = 0; i<y; i++)

{

for (j = 0; j<x; j++)

{

if (maze[i][j] == WALL)

{

printf("#");

}

else

printf(" ");

}

printf("\n");

}

int make_map()

{

int step, i, direction_temp, count = 0, d;

maze[maker.y][maker.x] = sign;

for (i = 0; i<4; i++)

{

if (can_go(maker.x + 2 * direction[i].x, maker.y + 2 * direction[i].y))

{

count++;

}

if (count == 0)

return 0;

step = rand() % 3 + 1;

direction_temp = rand() % 4;

for (i = 0; i<step; i++)

{

if (can_go(maker.x + 2 * direction[direction_temp].x, maker.y + 2 * direction[direction_temp].y))

{

maze[maker.y + direction[direction_temp].y][maker.x + direction[direction_temp].x] = sign;

maze[maker.y + 2 * direction[direction_temp].y][maker.x + 2 * direction[direction_temp].x] = sign;

maker.x += 2 * direction[direction_temp].x;

maker.y += 2 * direction[direction_temp].y;

}

else

{

d = rand() % 4;

direction_temp = d;

}

return 1;

}

int com_map()

{

int i;

for (i = 0; i<4; i++)

{

if (can_set(maker.x + 2 * direction[i].x, maker.y + 2 * direction[i].y))

{

maze[maker.y + direction[i].y][maker.x + direction[i].x] = sign + 1;

return 1;

}

return 0;

}

int make_map_dps()

{

int step, i, direction_temp, count = 0, d;

maze[maker.y][maker.x] = 1;

if (maker_n == 100)

{

printf_pad();

getchar();

closegraph();

exit(0);

}

for (i = 0; i<4; i++)

{

if (can_go(maker.x + 2 * direction[i].x, maker.y + 2 * direction[i].y))

{

count++;

}

if (count == 0)

return 0;

step = rand() % 3 + 1;

direction_temp = rand() % 4;

for (i = 0; i<step; i++)

{

if (can_go(maker.x + 2 * direction[direction_temp].x, maker.y + 2 * direction[direction_temp].y))

{

maze[maker.y + direction[direction_temp].y][maker.x + direction[direction_temp].x] = sign;

maze[maker.y + 2 * direction[direction_temp].y][maker.x + 2 * direction[direction_temp].x] = sign;

maker.x += 2 * direction[direction_temp].x;

maker.y += 2 * direction[direction_temp].y;

maker_step[++i_maker_step] = direction_temp + 1;

maker_n++;

}

else

{

d = rand() % 4;

direction_temp = d;

}

return 1;

}

int move_back()

{

int i;

if (i_maker_step<0 || i_maker_step >= mx*my)

exit(0);

i = maker_step[i_maker_step--] - 1;

maker.y = maker.y - 2 * direction[i].y;

maker.x = maker.x - 2 * direction[i].x;

return 1;

}

int main()

{

int i, j, x, y, s, e, maker_total;

int *p_temp;

char str[10];

setinitmode(NULL);

initgraph(400, 300);

setcaption("MAZE");

inputbox_getline("请输入迷宫的大小", "请输入一个数字，输入完请回车", str, sizeof(str) / sizeof(*str));

mx = my = atoi(str);

if (mx<1 || mx>200)

{

mx = MX;

my = MY;

_x = _X;

_y = _Y;

}

else

{

_x = mx * 2 + 1;

_y = my * 2 + 1;

}

maker_total = mx*my;

x = mx * 2 + 1;

y = my * 2 + 1;

closegraph();

maker_step = (int *)calloc(mx*my, sizeof(int));

maze = (int **)calloc(y, sizeof(int *));

p_temp = (int *)calloc(x*y, sizeof(int));

for (i = 0; i<y; i++)

{

maze[i] = p_temp + x*i;

}

for (i = 0; i<y; i++)

{

for (j = 0; j<x; j++)

{

maze[i][j] = !(j % 2) || !(i % 2) || i == 0 || i == y - 1 ? WALL : 0;

}

maker.y = 1;

maker.x = 1;

srand(time(NULL));

while (maker_n != maker_total)

{

while (make_map_dps())

;

move_back();

}

/* while (!is_map_created())

{

while (make_map())

;

sign++;

maker = temp;

if (sign >= 3)

com_map();

}

maker = temp;

if (sign >= 3)

com_map();*/

for (i = 0; i<y; i++)

for (j = 0; j<x; j++)

if (maze[i][j]>0)

maze[i][j] = 0;

srand(time(NULL));

s = rand() % (mx);

e = rand() % (mx);

explorer.x = 2 * s + 1;

explorer.y = 0;

maze[0][2 * s + 1] = START;

maze[y - 1][2 * e + 1] = END;

printf_pad();

//move(1);

return 0;

}

《C 程序设计专题》Project

2016年3月1日 by Lnyan·2条评论

（待下次有空时再将剩余的几个发上来(⊙﹏⊙)

趁着刚刚开学，事情并不算太多（其实也不少），把去年自己写的 C 程序设计专题的 Project 都发上来，为这一级的学弟学妹们提供参考吧。

模块化程序设计与递归函数专题（迷宫寻径或八皇后问题）: Maze-Project
链表及其操作和应用专题（多项式计算器）：Polynomial-Project
图形化程序设计专题（俄罗斯方块或打字游戏）：Tetris-Project
算法专题（快速排序与插入排序）：Sorting-Project

然而，时隔一年（应该是过去了一个学期），却发现自己并没有太大的进步，真是一种糟糕的感受。

上个学期真的是因为生病而整个荒废掉了，几乎没有什么长进，sigh~

整数的划分

2015年8月31日 by Lnyan·0评论

很久以前的一份作业，似乎今年3月份时做的，都忘了思路了……

编程求某一个正整数的所有划分数。如输入6，则输出：

6 = 5+1
6 = 4+2
6 = 4+1+1
6 = 3+3
6 = 3+2+1
6 = 3+1+1+1
6 = 2+2+2
6 = 2+2+1+1
6 = 2+1+1+1+1
6 = 1+1+1+1+1+1

题目要求大致就是这样子，原题目要求是递归实现，但忘了为何我最后使用了迭代+链表实现了，反正不是自己要交的作业~ 代码如下~

有同学今年修了这门课，他来问我这道题，给他讲了递归版，顺手发上来吧。

继续阅读

非递归式汉诺塔的C语言实现

2015年3月12日 by Lnyan·0评论

　　用链表和迭代的思维实现的汉诺塔，循环次数太多，效率有些差，但总是比递归要好一些的。
　　思路是：在任何条件下，需要被移动的圆盘以及其被移动的目标位置都是可知且唯一的，所以可以通过迭代的方式实现。
　　代码如下：
继续阅读

Lnyan's Blog

Stand out to be outstanding

分类：C

LeetCode-338. Counting Bits

2015-06-图形化程序设计-打字游戏与俄罗斯方块

背景

打字游戏

俄罗斯方块v20150614

俄罗斯方块v20150628

报告及源码

一、问题说明

二、算法设计与说明

三、数据结构设计与说明

四、系统设计难点与解决方案

1、难点：

2、解决方案（与难点对应）：

五、人员分工说明

六、源码

2015-04-多项式运算链表实现

背景

报告及源码

2015-03-迷宫寻径-Maze-Project

相关背景

效果图

感想

具体实现及思路

源码

《C 程序设计专题》Project

整数的划分

非递归式汉诺塔的C语言实现

墙	起	墙	墙	墙
墙	空	墙	空	终
墙	空	墙	空	墙
墙	空	空	空	墙
墙	墙	墙	墙	墙

墙	起	墙	墙	墙
墙	空	墙	空	终
墙	空	墙	空	墙
墙	空	空	空	墙
墙	墙	墙	墙	墙

墙	起	墙	墙	墙
墙	空	墙	空	终
墙	空	墙	空	墙
墙	空	空	空	墙
墙	墙	墙	墙	墙