대기 열 을 이용 하여 미궁 구 해 최 단 경로 실현

26981 단어 데이터 구조
#include "pch.h"
#include 
using namespace std;
struct point
{
	int x;
    int y;
	point *front;//     
};

int aspect[4][2] = {//    
	{0,-1},
	{1,0},
	{-1,0},
    {0,1}};
int main()
{
	cout << "  8*8   (1   ,0    ):" << endl;
	int a[8][8] = {
	{0,0,1,1,0,1,0,1},
	{0,0,0,0,1,1,0,1},
	{0,0,0,1,0,0,1,0},
	{1,0,0,0,1,1,0,0},
	{1,1,1,0,0,0,1,1},
	{0,0,0,0,0,1,0,1},
	{0,1,0,0,0,0,1,0},
	{0,0,0,1,0,0,0,0} };
	for (int i = 0; i < 8; i++)//    
	{
		for (int j = 0; j < 8; j++)
			cout << a[i][j] << "\t";
		cout << endl;
	}
	point *start = new point;
	point *end = new point;
	start->x = 0;
	start->y = 0;
	start->front = start;
	end->x = 7;
	end->y = 7;
	int f=0,r=1;
	point *Qu[100];
	Qu[f]=start;//f=0
	a[start->x][start->y]= -1;
	cout <<"   :"<< end->x+1 << "," << end->y+1 << endl;
	
	point *front = new point;
	point *next = new point;
	int X=0, Y=0;
	int flag = 0;
	while (f<=r)
	{
		flag = 0;
		front = Qu[f];//   f=0 f=1
		f++;
		if (front->x == end->x&& front->y == end->y)//      
		{
			cout << "    !"<<endl;
			point *temp = front;
			while (temp->x != start->x||temp->y != start->y)
			{
				cout << "(" << temp->x+1 << "," << temp->y+1 << ")" << endl;
				temp = temp->front;
			}
			cout<< "(" << start->x+1 << "," << start->y+1<< ")" << endl;
			break;
		}
		else //         
		{
			for (int i = 0; i < 4; i++)
			{
				X = front->x + aspect[i][0];
				Y = front->y + aspect[i][1];
				if ((X< 8) && (Y< 8) && (X >=0) && (Y >= 0))
				{
					if (a[X][Y]==0)
					{
						next = new point;
						flag = 1;
						a[X][Y] = -1;//    
						next->x = X;
						next->y = Y;
						next->front = front;
						Qu[r] = next;
						r++;
					}
				}
			}
		}
		if (flag == 0)
			a[X][Y] == 1;
	}
	for (int i = 0; i < 8; i++)//     
		for (int j = 0; j < 8; j++)
		{
			if (a[i][j] == 0)
				a[i][j] = 1;
			if (a[i][j] == -1)
				a[i][j] = 0;
		}
	for (int i = 0; i < 8; i++)//    
	{
		for (int j = 0; j < 8; j++)
			cout << a[i][j] << "\t";
		cout << endl;
	}
	cout << "—————————   —————————————"<<endl;
}

좋은 웹페이지 즐겨찾기