#include
#include
#include
#include
#include
using?namespace?std;
using?std::queue;
using?std::stack;
typedef?struct?Point
{
	int?x;
	int?y;
	int?d;//方向?若方向為-1，則表示起點
}Point;
queue?mqueue;
stack?mstack;
Point?pos?pos1;
int?m?n;//迷宮行（tm-1）/2和列（tn-1）/2
int?tm?tn;//實際作圖
int?x?y?tx1?tx2?ty1?ty2;//點坐標
int?d;
int?s[10000000];
int?maze[1000][1000]?mark[1000][1000];//最大迷宮
int?sign[4][2]?=?{?{?-10?}{?10?}{?0-1?}{?01?}?};//上下左右四個方向?0上?1下?2上?3下
Point?start;
int?Find_x（int?x）;
void?unionSets（int?node1?int?node2）;
void?Init（）;
int?getAdd（int?x?int?y）;
void?foundpath（）;
void?fixmaze（）;
int?connected（int?node1?int?node2）;
void?Findpath（）;
void?changemaze（）;
int?main（）
{
	Init（）;
	cout?<	cin?>>?m?>>?n;
	tm?=?m?*?2?+?1;
	tn?=?n?*?2?+?1;
	start.x?=?1;
	start.y?=?1;
	start.d?=?-1;
	mqueue.push（start）;
	for?（int?i?=?0;?i?	{
		for?（int?j?=?0;?j?		{
			maze[i][j]?=?1;
			mark[i][j]?=?0;
		}
	}
	for?（int?i?=?1;?i?	{
		for?（int?j?=?1;?j?			maze[i][j]?=?0;
	}
	srand（time（NULL））;
	foundpath（）;
	fixmaze（）;
	cout?<	for?（int?i?=?0;?i?	{
		for?（int?j?=?0;?j?		{
			if?（maze[i][j]?==?1）
				cout?<			else?if?（maze[i][j]?==?0）?cout?<		}
		cout?<	}
	Findpath（）;
	changemaze（）;
	cout?<	for?（int?i?=?0;?i?	{
		for?（int?j?=?0;?j?		{
			if?（maze[i][j]?==?1）
				cout?<			else?if?（maze[i][j]?==?0）?cout?<			else?if?（maze[i][j]?==?-1）?cout?<
		}
		cout?<	}
	system（“pause“）;
	return?0;
}
int?connected（int?node1?int?node2）
{
	return?Find_x（node1）?==?Find_x（node2）;
}
int?Find_x（int?x）
{
	if?（s[x]?		return?x;
	else
		return?Find_x（s[x]）;


};
void?unionSets（int?node1?int?node2）
{
	int?root1?=?Find_x（node1）;
	int?root2?=?Find_x（node2）;
	if?（root1?==?root2）
		return;
	if?（s[root2]?		s[root1]?=?root2;
	else?{
		if?（s[root1]?==?s[root2]）
			s[root1]--;
		s[root2]?=?root1;
	}
};
int?getAdd（int?x?int?y）
{
	return?（x*tn?+?y）;
};
void?Init（）
{
	for?（int?i?=?0;?i?		s[i]?=?-1;
};
void?foundpath（）
{
	while?（connected（getAdd（1?1）?getAdd（tm?-?2?tn?-?2））?!=?1）
	{
		do
		{
			x?=?rand（）?%?（tm?-?2）?+?1;
			y?=?rand（）?%?（tn?-?2）?+?1;
		}?while?（maze[x][y]?==?0）;
		d?=?x?%?2;
		if?（d?==?0）
		{
			tx1?=?x?+?1;
			ty1?=?y;
			tx2?=?x?-?1;
			ty2?=?y;
			if?（connected（getAdd（tx1?ty1）?getAdd（tx2?ty2））?!=?1）
			{
				maze[x][y]?=?0;
				unionSets（Find_x（getAdd（tx1?ty1））?Find_x（getAdd（tx2?ty2）））;
			}
		}
		else?if?（d?==?1）
		{
			tx1?=?x;
			ty1?=?y?+?1;
			tx2?=?x;
			ty2?=?y?-?1;
			if?（connected（getAdd（tx1?ty1）?getAdd（tx2?ty2））?!=?1）
			{
				maze[x][y]?=?0;
				unionSets（Find_x（getAdd（tx1?ty1））?Find_x（get