ダイクストラ法を実装しようズ

# include <Siv3D.hpp> // Siv3D v0.6.14
#include <numeric>
#include <stack>
#include <queue>
#include <map>
 
using std::pair;
 
 
const Size BLOCK_SIZE{ 32, 32 };//ブロック一個の表示の大きさ
const Size MazeSize{ 25, 19 };//サイズは奇数でなければいけない
const Point Start{ 1,1 };
const Point Goal{ MazeSize.x - 2, MazeSize.y - 2 };
const float Div{ 5.0 }; //何段階でウェイト（コスト）を分割するか
 
const Vec2 dirs[4]{ {0,1},{0,-1},{1,0},{-1,0} };
 
enum OBJS
{
	WALL, BAR, FLOOR, START, GOAL, MAX_OBJS
};
 
struct floorData
{
	OBJS type;
	int  weight;
};
 
 
 
//二次元配列　MazeData[MazeSize.y][MazeSize.x]{FLOORで初期化｝
std::vector<std::vector<floorData>> MazeData(MazeSize.y, std::vector<floorData>(MazeSize.x, {FLOOR, 0})); //迷路そのもの
std::vector<std::vector<int>> dist(MazeSize.y, std::vector<int>(MazeSize.x, INT_MAX)); //ダイクストラ法のコスト保存用
std::vector<std::vector<Vec2>> pre(MazeSize.y, std::vector<Vec2>(MazeSize.x, {-1, -1})); //経路保存用
 
 
 
 
void MakeWall();//外壁と、迷路の壁を作る
void MakeMaze();//迷路を作る
void DrawMaze();//迷路を書く
 
 
void MakeMaze()
{
	for (int j = 0; j < MazeSize.y; j++)
	{
		for (int i = 0; i < MazeSize.x; i++)
		{
			if (i == 0 || j == 0 || i == MazeSize.x - 1 || j == MazeSize.y - 1)
				continue;
			MazeData[j][i].weight = rand() % (int)(Div) + 1;
		}
	}
}
 
 
void MakeWall()
{
	for (int j = 0; j < MazeSize.y; j++)
	{
		for (int i = 0; i < MazeSize.x; i++)
		{
			if (i == 0 || j == 0 || i == MazeSize.x - 1 || j == MazeSize.y - 1)
				MazeData[j][i].type = WALL;
			continue;
		}
	}
	int bars[2]{ MazeSize.x * 1.0 / 3.0, MazeSize.x * 2 / 3 };
 
	for (int j = 0; j < MazeSize.y * (2.0 / 3.0); j++)
	{
		for (int i = 0; i < 2; i++)
		{
			int m = j;
			if (i == 1)
				m = MazeSize.y - j -1;
			MazeData[m][bars[i]].type = WALL;
		}
	}
}
 
void SetSG()
{
	MazeData[Start.y][Start.x].type = START;
	MazeData[Goal.y][Goal.x].type = GOAL;
}
 
 
void DrawMaze()
{
	for (int j = 0; j < MazeSize.y; j++)
	{
		for (int i = 0; i < MazeSize.x; i++)
		{
			bool drawFrame = false;
			Color col = Color{ 0,0,0 };
			switch (MazeData[j][i].type)
			{
			case WALL:
				col = Palette::Firebrick;
				break;
			case FLOOR:
				col = Color{ 0, (unsigned char)(255.0 * (1.0 - MazeData[j][i].weight / Div)), 0 };
				break;
			case START:
			case GOAL:
				col = Palette::Yellow;
				drawFrame = true;
				break;
			case BAR:
			default:
				col = Palette::Black;
			}
			Rect{ i * BLOCK_SIZE.x, j * BLOCK_SIZE.y, BLOCK_SIZE }.draw(col);
			if(drawFrame)
				Rect{ i * BLOCK_SIZE.x, j * BLOCK_SIZE.y, BLOCK_SIZE }.drawFrame(1, 1, Palette::Red);
			if(dist[j][i] < INT_MAX)
			FontAsset(U"NUM")(ToString(dist[j][i]))
				.drawAt(i * BLOCK_SIZE.x + BLOCK_SIZE.x / 2, j * BLOCK_SIZE.y + BLOCK_SIZE.y / 2, Palette::Black);
		}
	}
}
 
void Main()
{
	FontAsset::Register(U"NUM", 14, Typeface::Medium);
 
	srand((unsigned int)time(nullptr));
	// 背景の色を設定する | Set the background color
	Scene::SetBackground(Palette::Cornflowerblue);
 
	MakeMaze();
	MakeWall();
	SetSG();
 
	//Dijkstra({ Start.x, Start.y });　//ダイクストラ法でStart.x,Start.yから全探索(つくれ）
	//std::vector<Vec2> route = restore(Goal.x, Goal.y);//経路を逆追跡して、経路の配列を作る(つくれ）
	while (System::Update())
	{
		DrawMaze();//迷路の描画
		//for (auto itr: route) //経路を一個ずつピンクで囲む
		//{
		//	
		//	Rect{(int)itr.x * BLOCK_SIZE.x, (int)itr.y * BLOCK_SIZE.y, BLOCK_SIZE }.drawFrame(3, Palette::Hotpink);
		//}
	}
}