スタートからの距離と壁を距離の最大値の桁数に合わせて出力する。
using System;
using System.Collections.Generic;
using System.Linq;
public class Maze {
public const int PATH = 0;
public const int WALL = 1;
public int width;
public int height;
public int[,] maze;
public int[,] dist;
public int[] start;
public int[] goal;
private Random random;
public Maze(int width, int height, int seed = 0) {
this.width = width;
this.height = height;
if (this.width < 5 || this.height < 5) {
Environment.Exit(0);
}
if (this.width % 2 == 0) {
this.width++;
}
if (this.height % 2 == 0) {
this.height++;
}
this.maze = new int[this.height,this.width];
for (int y = 0; y < this.height; ++y) {
for (int x = 0; x < this.width; ++x) {
this.maze[y,x] = Maze.PATH;
}
}
this.dist = new int[this.height,this.width];
for (int y = 0; y < this.height; ++y) {
for (int x = 0; x < this.width; ++x) {
this.dist[y,x] = -1;
}
}
this.start = new int[] {1, 1};
this.goal = new int[] {this.width-2, this.height-2};
this.random = new Random(seed);
}
public int[,] set_outer_wall() {
for (int y = 0; y < this.height; ++y) {
for (int x = 0; x < this.width; ++x) {
if (x == 0 || y == 0 || x == this.width-1 || y == this.height-1) {
this.maze[y,x] = Maze.WALL;
}
}
}
return this.maze;
}
public int[,] set_inner_wall() {
for (int y = 2; y < this.height-1; y += 2) {
for (int x = 2; x < this.width-1; x += 2) {
this.maze[y,x] = Maze.WALL;
}
}
return this.maze;
}
public int[,] set_maze_boutaoshi() {
int wall_x;
int wall_y;
int direction;
this.set_outer_wall();
this.set_inner_wall();
for (int y = 2; y < this.height-1; y += 2) {
for (int x = 2; x < this.width-1; x += 2) {
while (true) {
wall_x = x;
wall_y = y;
if (y == 2) {
direction = random.Next(0,4);
} else {
direction = random.Next(0,3);
}
switch (direction) {
case 0:
wall_x += 1;
break;
case 1:
wall_y +=1;
break;
case 2:
wall_x -=1;
break;
case 3:
wall_y -=1;
break;
}
if (this.maze[wall_y,wall_x] != Maze.WALL) {
this.maze[wall_y,wall_x] = Maze.WALL;
break;
}
}
}
}
return this.maze;
}
public int[,] set_start_goal(int[] start, int[] goal) {
if (this.maze[start[1],start[0]] == Maze.PATH) {
this.start = start;
}
if (this.maze[goal[1],goal[0]] == Maze.PATH) {
this.goal = goal;
}
return this.maze;
}
public int[,] set_dist_bfs(bool flag = false) {
int[] point;
int[,] x = new int[,] {{0,-1},{1,0},{0,1},{-1,0}};
Queue<int[]> queue = new Queue<int[]>();
this.dist[this.start[1],this.start[0]] = 0;
queue.Enqueue(this.start);
while (queue.Count > 0) {
point = queue.Dequeue();
for (int i = 0; i < x.GetLength(0); ++i) {
if (this.maze[point[1]+x[i,1],point[0]+x[i,0]] == 0 && this.dist[point[1]+x[i,1],point[0]+x[i,0]] == -1) {
this.dist[point[1]+x[i,1],point[0]+x[i,0]] = this.dist[point[1],point[0]] + 1;
queue.Enqueue(new int[] {point[0]+x[i,0],point[1]+x[i,1]});
}
if (flag != true) {
if (point[0]+x[i,0] == this.goal[0] && point[1]+x[i,1] == this.goal[1]) {
queue.Clear();
break;
}
}
}
}
return this.dist;
}
public int[,] set_dist_dfs(bool flag = false) {
int[] point;
int[,] x = new int[,] {{0,-1},{1,0},{0,1},{-1,0}};
Stack<int[]> stack = new Stack<int[]>();
this.dist[this.start[1],this.start[0]] = 0;
stack.Push(this.start);
while (stack.Count > 0) {
point = stack.Pop();
for (int i = 0; i < x.GetLength(0); ++i) {
if (this.maze[point[1]+x[i,1],point[0]+x[i,0]] == 0 && this.dist[point[1]+x[i,1],point[0]+x[i,0]] == -1) {
this.dist[point[1]+x[i,1],point[0]+x[i,0]] = this.dist[point[1],point[0]] + 1;
stack.Push(new int[] {point[0]+x[i,0],point[1]+x[i,1]});
}
if (flag != true) {
if (point[0]+x[i,0] == this.goal[0] && point[1]+x[i,1] == this.goal[1]) {
stack.Clear();
break;
}
}
}
}
return this.dist;
}
public int[,] set_shortest_path() {
int[] point;
int[,] x = new int[,] {{0,-1},{1,0},{0,1},{-1,0}};
point = this.goal;
this.maze[point[1],point[0]] = '*';
while (this.dist[point[1],point[0]] > 0) {
for (int i = 0; i < x.GetLength(0); ++i) {
if (this.dist[point[1],point[0]]-this.dist[point[1]+x[i,1],point[0]+x[i,0]] == 1) {
if (this.dist[point[1],point[0]] > 0) {
this.maze[point[1]+x[i,1],point[0]+x[i,0]] = '*';
point = new int[] {point[0]+x[i,0],point[1]+x[i,1]};
}
}
}
}
return this.maze;
}
public void print_maze() {
this.maze[this.start[1],this.start[0]] = 'S';
this.maze[this.goal[1],this.goal[0]] = 'G';
for (int y = 0; y < this.maze.GetLength(0); ++y) {
for (int x = 0; x < this.maze.GetLength(1); ++x) {
if (this.maze[y,x] == Maze.WALL) {
Console.Write('#');
} else if (this.maze[y,x] == Maze.PATH) {
Console.Write(' ');
} else if (this.maze[y,x] == 'S') {
Console.Write('S');
} else if (this.maze[y,x] == 'G') {
Console.Write('G');
} else if (this.maze[y,x] == '*') {
Console.Write('*');
}
}
Console.WriteLine();
}
}
public void print_dist() {
for (int y = 0; y < this.dist.GetLength(0); ++y) {
for (int x = 0; x < this.dist.GetLength(1); ++x) {
if (this.dist[y,x] == -1) {
if (this.dist.Cast<int>().Max() == -1) {
Console.Write('#');
} else {
for (int i = 0; i < this.dist.Cast<int>().Max().ToString().Length; ++i) {
Console.Write('#');
}
}
} else {
if (this.dist[y,x].ToString().Length == this.dist.Cast<int>().Max().ToString().Length) {
Console.Write(this.dist[y,x]);
} else {
for (int i = 0; i < this.dist.Cast<int>().Max().ToString().Length-this.dist[y,x].ToString().Length; ++i) {
Console.Write(' ');
}
Console.Write(this.dist[y,x]);
}
}
}
Console.WriteLine();
}
}
public static void Main() {
Maze maze1 = new Maze(15, 15);
maze1.set_maze_boutaoshi();
maze1.set_start_goal(new int[] {9, 5}, new int[] {9, 11});
maze1.set_dist_bfs(true);
maze1.print_dist();
}
}
今回は、以下のように出力される。
##############################
##121110## 8##1413121314##16##
###### 9## 7######11######15##
##10 9 8 7 6 7 8 91011121314##
##11###### 5##########13##15##
##12## 6 5 4 3 2 1 0##14##16##
##13###### 5##############17##
##14## 8 7 6 7 8 9101112##18##
########## 7## 9##########19##
##121110 9 8##1011121314##20##
##13##########11######15##21##
##141516##1413121314##16##22##
######17######13##########23##
##201918##16151415161718##24##
##############################
