通过alpha-belta剪枝的极大极小值算法实现简单的五子棋+A*算法与IDA*算法解决走迷宫问题

通过alpha-belta剪枝的极大极小值算法实现简单的五子棋+A*算法与IDA*算法解决走迷宫问题

#include
#include
#include
#include
#include 
#include
#include
#include
#include
#include 
#include

using namespace std;


typedef  struct point{
	int xy;
	int fxgxhx;
	int pxpy;
	bool visited;
	struct point *next;
}*Point;

Point Qpath;
int entry_xentry_y;
int exit_xexit_y;
int rowcol;
int maze[200][200];
int Visited[200][200];
char Path[200][200];
char PATH[200];


int Manhattan_dis（int x int y）{
	return abs（x - exit_x） + abs（y - exit_y）;
}


bool QueueEmpty（Point Q）{
	if（Q->next == NULL） return true;
	return false;
}

void EnQueue（Point QPoint q）{
	if（QueueEmpty（Q））{
		Q->next=q;
		return;
	}
	Point p = Q->next;
	while（p->next!=NULL&&p->fx < q->fx）
		p = p->next;
	q->next = p->next;
	p->next = q;
	Visited[q->x][q->y] = 1;
}

void EnQueue_1（Point QPoint q）{
	if（QueueEmpty（Q））{
		Q->next=q;
		return;
	}
	Point p = Q->next;
	while（p->next!=NULL&&p->fx > q->fx）
		p = p->next;
	q->next = p->next;
	p->next = q;
}

void DeQueue（Point QPoint &p）{
	p = Q->next;
	Q->next=p->next;
}
			
void Build_Maze（char *filename）{
	ifstream in;
	string input;
	in.open（filename）;
	int depth = 0;
	int flag = 0 m = -1;
	while（getline（ininput））{
		int length = input.length（）;
		int i = 0j = 0;
		while（i < length）{
			if（input[i] == ‘0‘） maze[depth][j++] = 0;
			else if（input[i] == ‘1‘） maze[depth][j++] = 1;
			i++;
		}
		depth++;
		if（m < j） m = j;
		if（m > j） flag = 1;
	}
	col = depth - flag; row = m;
}

void Get_entry_and_exit（）{
	int i;
	for（i = 0; i < row; i++）{
		if（maze[0][i] == 0）{
			entry_x = 0;
			entry_y = i;
		}
		if（maze[col - 1][i] == 0）{
			exit_x = col - 1;
			exit_y = i;
		}
	}
	for（int j = 0; j < col; j++）{
		if（maze[j][0] == 0）{
			entry_x = j;
			entry_y = 0;
		}
		if（maze[j][row - 1] == 0）{
			exit_x = j;
			exit_y = row - 1;
		} 
	} 
}

Point Generate_Point（int x int y int gx int px int py）{
	Point Entry = （Point）malloc（sizeof（point））;
	Entry->x = x;Entry->y = y;
	Entry->px = px; Entry->py = py;
	Entry->gx = gx; Entry->hx = Manhattan_dis（entry_xentry_y）;Entry->fx = Entry->gx + Entry->hx;
	Entry->next = NULL;
	return Entry;
}
	
void A_STAR（）{
	Q = Generate_Point（-1-10-1-1）;
	path = Generate_Point（-1-10-1-1）;
	Point Entry = Generate_Point（entry_xentry_y0-1-1）;
	EnQueue（QEntry）;
	Point p = （Point）malloc（sizeof（point））;
	while（!QueueEmpty（Q））{
		DeQueue（Qp）;
		EnQueue_1（pathp）;
		if（p->x == exit_x && p->y == exit_y）{
			return;
		}
		int x = p->x y = p->y gx = p->gx;
		if（ x + 1 < col && maze[x+1][y] == 0 && Visited[x+1][y] == 0）{
			Point q = Generate_Point（x + 1 y gx + 1 x y）;
			EnQueue（Qq）;
		}
		if（ y + 1 < row && maze[x][y+1] == 0 && Visited[x][y+1] == 0）{
			Point q = Generate_Point（x y + 1 gx + 1 x y）;
			EnQueue（Qq）;
		}
		if（ x - 1 >= 0 && maze[x-1][

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        4673  2019-05-12 16:41  ai_1.1.cpp
     文件        5707  2019-05-12 16:40  ai_1.2.cpp
     文件       12251  2019-06-21 17:02  ai_2.cpp
     文件         916  2019-05-12 00:44  input1.txt
     文件        3647  2019-05-12 14:09  input2.txt
     文件         122  2019-06-21 17:04  output.txt
     文件          55  2019-05-12 16:31  output_astar_1.txt
     文件         133  2019-05-12 16:36  output_astar_2.txt
     文件          56  2019-05-12 20:16  output_ida_1.txt
     文件         133  2019-05-12 16:36  output_ida_2.txt